В данной темке я хотел бы узнать парочку вопросов, по поводу решения некоторых задач.
Начну с начала :) Первый вопрос возник уже на 2-ой задачке, а именно.
Условия задачки 2:
Некоторое царство-государство окружено крепостной стеной с башнями, в которых
расположены дозорные. Для оперативного оповещения каждого дозорного между башнями
решили установить прямую телефонную. Ограниченная стеной территория царства-государства
представляет собой многоугольник ненулевой площади произвольного вида без самопересечений,
башни располагаются в его вершинах.
Можно ли построить такую прямую связь, соединяющую каждую башню с каждой, чтобы
кабель не проходил вне территории царства-государства.
Входные данные:
В первой строке входного файла записано одно целое число ― количество тестов, не более
10. Описание каждого теста состит из двух строк, в первой строке указано одно целое число —
количество башен N (3 ≤ N ≤ 1000). Во второй строке через пробел перечислены целочисленные
координаты башен по порядку их следования друг за другом, начиная с произвольной. Для
каждой башни сначала указывается координата x, а затем y. Координаты по модулю не
превосходят 10^5. Считаем, что первая из перечисленных башен всегда соединена крепостной
стеной с последней.
Выходные данные:
В выходной файл для каждого теста на отдельной строке необходимо вывести слово yes,
если возможно построить такую связь, или no в случае невозможности таковой.
Я решил банально перебрать векторным произведением эти точки и проверить оболочку на выпуклость. Даёт 98 баллов, падает на 1 тесте. Интересно на каком? Если кто-нибудь знает, где валится данное решение — напишите, буду искренне Вам благодарен!
Задачка номер 5. Условия:
Емеля, женившись на Несмеяне, получил полцарства в придачу. Захотелось ему осмотреть
свои владения. Открыл он карту. Сколько на ней деревень, поселков и городов обозначено!
Хочется ему как можно большее количество этих населенных пунктов посетить. Только вот одна
проблема: хоть и быстроходная печь у Емели и вездеходная, но имеет один маленький
конструктивный недостаток — не умеет печка поворачивать. “Ничего, — подумал Емеля, — доеду
я до какой-нибудь окраинной деревеньки, там разверну печку, как надо, а затем прямиком через
все государство прокачусь!”
Помогите Емеле посчитать максимальное количество населенных пунктов, через которые
он может проехать, не сворачивая.
Входные данные
Входной файл состоит из N+1 строки (0 < N < 1000). В первой строке записано число N —
количество населенных пунктов на карте. В каждой следующей строке через пробел записано по
два целых числа — координаты населенного пункта на карте, все координаты по модулю не
превосходят 10^5.
Выходные данные
В выходном файле должно быть одно целое число — максимальное количество населенных
пунктов, через которые может проехать Емеля на своей печке.
Я решал следующим образом:
1.Bыразил **k**__ , выразил **b**__ (y=kx+b). И составил массив из паросочетаний прямых.( Всего ~ n*n/2 Прямых).
2.Далее отсортировал и проверял соседние _k_**** и _b_****, если они совпадали => Точки лежат на 1-ой прямой.
3.Данное решение не давало 100 баллов, лично я думаю, что дело в точности, точность подсчёта сказалась, но точно не уверен.
4.Очень хотелось бы услышать, **как решалась данная проблема**, без вычислений( чтобы погрешность не имела значений), если это возможно. Или просто способ, как можно было решить эту проблему?
Еще хотелось бы узнать, как решались задачки 10 и 8. Условия :
Задача 10. Суперсвадьба
Ограничение по времени: 1 секунда на тест
Съемки сериала «Любовь любителей любви» подходят к концу, и сценаристы решили
поместить в конец сериала суперсвадьбу. Под суперсвадьбой понимается одновременное
проведение N свадеб между N мужчинами и N женщинами. Для каждого мужчины и каждой
женщины известно, могут ли они пожениться. Продюсера сериала заинтересовал вопрос: четно ли
число возможных суперсвадеб? Напишите программу, которая ответит на этот вопрос.
Входные данные:
В первой строке входного файла записано одно целое число ― количество тестов, не более
10. Описание каждого теста состоит из нескольких строк. Сначало в отдельной строке входного
файла записано число целое N (1 ≤ N ≤ 100). В каждой из следующих N строк через пробел
записано по N чисел. Эти числа задают таблицу размера N x N, где j-ое число в i-й строке равно 1
тогда и только тогда, когда мужчина номер i и женщина номер j могут пожениться в конце
сериала, в противном случае на этом месте стоит 0.
Выходные данные:
В выходной файл для каждого теста в отдельной строке нужно вывести EVEN, если
количество возможных суперсвадеб четно, и ODD — в противном случае.
К данной задачке я не приступал, не было времени, да и идей как таковых.
И задачка 8. Условия:
Гондор — один из последних оплотов сил, противостоящих Мордору. Гондору угрожает
серьёзная опасность. Орки продолжают свои набеги, и силы защитников тают. Чтобы спасти
положение Арагорн, потомственный король Гондора, отправляется в долину мертвых, чтобы
призвать души мертвых выполнить их долг перед королями Гондора. Легенды гласят, что никто
живым не возвращался оттуда. На входе Арагорн увидел руны, гласящие, что мертвые при
помощи магии научились делать хроноколодцы, позволяющие им путешествовать во времени.
Хроноколодец — это образование, которое имеет фиксированные пространственные
координаты и осуществляет перенос по некотрому промежутку времени. Любой объект, попавший
в хроноколодец, переносится во времени к его началу. Начало колодца может быть либо ниже во
времени конца — тогда он действует в прошлое, либо выше — тогда он действует в будущее.
Однако проклятье не даёт им покинуть долину. Несмотря на возможность путешествий во
времени, мертвые предпочитают жить в K-ом году по летоисчислению Гондора. Там же была
приведена схема расположения хроноколодцев. Хроноколодцами могут воспользоваться и
простые люди, вот только не каждый сможет пройти обратно тем же путём. Если на пути
Арагорна встречается хроноколодец, то он его может обойти без увеличения длины пути.
Поскольку долина большая, Арагорну хочется узнать, какое минимальное расстояние он пройдёт,
прежде чем сумеет найти мертвых. Помогите ему в этом.
Входные данные:
В первой строке входного файла записано число N — количество хроноколодцев
(1 <= N <= 5000). Во второй строке через пробел записаны два числа: текущий год по летосчислению
Гондора М и год назначения K. В третьей строке записаны координаты входа в долину. Если место
находится внутри хроноколодца, то Арагорн немедленно перемещается в его начало. В
следующих N строках записаны четвёрки целых чисел Xi, Yi, Starti, Endi — координаты i-го
хроноколодца, его начало и конец во времени (1 <= i <= N). Все координаты даны в метрах — это
целые числа, по модулю не превосходящие 10^4, все времена — целые числа, по модулю не
превосходящие 10^9. Гарантируется, что никакие два хроноколодца не имеют общих точек во
времени.
Выходные данные:
В выходном файле должно стоять единственное число — суммарная длина пройденного
Арагорном пути с точностью до 0.01. Если такого пути не существует, нужно вывести –1.
Я предположил, что тут что-то, связанное с потоками, а я с ними не знаком, к сожалению(((.
Огромнейшее спасибо каждому, кто поможет!
P.S Если у кого-то из участников олимпиады тоже есть вопросы по задачам, то смело задавайте их тут=)
