4 тур - з 07.11.16 по 13.11.2016
точка входу для відправлення розв'язків
http://134.249.159.199//cgi-bin/new-client?contest_id=36
Задача 1. Турпохід (20 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 2с.
Сергій вирішив організувати туристичний похід. А щоб було цікавіше, він своїм двом друзям Юрі і Валері повідомив лише часткову інформацію про дату походу, і якщо вони визначать точну дату походу, то всі разом відправляться в подорож.
Другу Юрі він особистим повідомленням в соціальній мережі повідомив число всередині місяця, а другу Валері – місяць походу. Потім Сергій опублікував на своїй сторінці список днів року, один з яких є точною датою походу, а також фразу про те, що Юра знає число, але не знає місяця, а Валера – знає місяць, але не знає числа.
Потім в коментарях відбувся наступний діалог:
Юра: Я не знаю точну дату походу, але впевнений, що і Валера також не знає.
Валера: Я спочатку не знав дату походу, але тепер після твого коментаря, знаю точно!
Юра: Ура! Тепер я також знаю точну дату туристичного походу і нарешті ми зустрінемося всі разом!
Коли ж друзі мають відправитися в похід?
Вхідні дані
В першому рядку міститься ціле число N (1≤N≤366) – кількість можливих дат, опублікованих Сергієм на своїй сторінці.
В кожному з наступних рядків міститься опис одної дати: число і номер місяця. Місяці пронумеровані від 1 до 12.
Дати приведені в хронологічному порядку всередині року.
Гарантується, що ситуація коректна, і існує єдино можлива дата туристичного походу, яка приводить до описаного діалогу.
Вихідні дані
Виведіть дату походу в такому форматі: спочатку число, а потім місяць.
Приклад
Вхідний файл
|
Вихідний файл
|
11
29 2
5 5
16 5
31 5
17 6
18 6
14 7
16 7
5 12
14 12
17 12
|
17 6
|
Задача 2. Червона Шапочка (100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
Червона Шапочка має якнайшвидше провідати свою хвору бабусю і віднести їй ліки та їжу. Її шлях пролягає через густий ліс, який розбитий на квадрати. З квадрата в квадрат можна попасти тільки рухаючись вверх, вниз, вліво або вправо. За межі лісу виходити не можна, ліс оточений непрохідним болотом. Ліс має форму прямокутника в якому N рядків і M стовпців. Червона Шапочка живе в лівому верхньому куті цього лісу, а її бабуся – в правому нижньому. Будинок бабусі охороняють мисливці. Тим лісом бродить Сірий Вовк, якого дуже треба остерігатися Червоній Шапочці. На щастя, початкове положення і маршрут його їй відомі.
За яку найменшу кількість кроків Червона Шапочка може досягнути своєї мети, дотримуючись при русі таких правил (крок – це переміщення з клітинки в сусідню клітинку):
1. Рухатися можна тільки в сусідню по горизонталі або вертикалі вільну клітину.
2. Переміщення здійснюється почергово: спочатку Сірий Вовк, потім Червона Шапочка.
3. Не допускається знаходження в одному квадраті Червоної шапочки та Сірого Вовка.
4. Ходи Червоної шапочки і Сірого Вовка обов’язкові.
5. Якщо ходи Сірого Вовка закінчилися, то він залишається в останній досягнутій клітині. Але наперед відомо, що він при цьому не заблокує шлях Червоної Шапочки до бабусі. Якщо Сірий Вовк досягнув фінішу (квадрата в якому живе бабуся), то його вбивають мисливці.
Вхідні дані
В першому рядку розмір поля: два числа через пропуск 0<N, M≤150. Далі йде N рядків в кожній з яких по M символів, що описують поле: крапка (.) – клітина вільна. Решітка (#) – непрохідна клітина. В наступному рядку два числа – номер рядка і стовпця, де спочатку знаходиться Сірий Вовк. Далі йде рядок з описом шляху Сірого Вовка: R – рух вправо, L – вліво, U – вверх, D – вниз. Кількість ходів суперника не більше 32000.
Вихідні дані
Єдине число – мінімальне число кроків, необхідне для досягнення фінішу.
Приклад:
Вхідний файл
|
Вихідний файл
|
3 5
.....
.#...
...#.
1 2
RRLDRRD
|
8
|
|