Завдання № 5
відбірково-тренувальних зборів
команди міста Києва

1. Таксомотор

Максимальна оцінка: 105 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: tax.in
Вихідний файл: tax.out
Програма: tax.*

У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд 1 до деякого натурального n.

Завдання
Створiть програму, яка визначить:

Вхідні дані
Перший рядок файлу мiстить у вказаному порядку такі натуральнi числа:
n — кiлькiсть зупинок, що не перевищує 250;
m — кiлькiсть маршрутiв;
t — кiлькiсть хвилин вiд початку доби, коли пасажир починає свiй рух;
a — номер зупинки, з якої вiн починає свiй рух;
b — номер зупинки, на яку вiн хоче потрапити.

Для j в межах вiд 1 до m включно ( j + 1)-ий рядок мiстить трiйки чисел. У кожнiй такiй трiйцi:

Загальна кiлькiсть ланок всiх маршрутiв не перевищує 7800.

Вихідні дані
Перший рядок файлу має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок файлу має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за 65432.

Приклад

tax.intax.out
7 4 1 7 3
3 2 0 4 35 1 2 50 1 3 70 1
5 5 0 6 15 1 4 30 1 5 45 1
7 2 0 2 5 11 6 10 1 7 20 1
7 60 0 2 70 1 6 80 1 7 90 1
70 12
1510 2



2. Гра «Ряд фішок»

Максимальна оцінка: 40 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: game.in
Вихідний файл: game.out
Програма: game.*

Скiнченну кiлькiсть фiшок розташовано в ряд i занумеровано послiдовними натуральними числами, починаючи з 1. Два гравцi по черзi забирають довiльнi одну або двi фiшки, розташованi поруч (номери яких вiдрiзняються на 1). Переможцем вважають того, хто примусить суперника зробити останнiй хiд.

Завдання
Створiть програму, яка для довiльної позицiї гри визначає всi виграшнi ходи — такi ходи, що ґарантують виграш (за умови правильного продовження гри зi свого боку) незалежно вiд ходiв суперника.

Вхідні дані
Файл мiстить номери наявних фiшок, якi меншi за 21.

Вихідні дані
Перший i другий рядки файлу мають мiстити (у довільному) порядку номери фiшок, забравши якi відповідно по однiй або разом з наступною по двi гравець робить виграшний хiд з позицiї, заданої вхiдними даними. Якщо таких ходiв немає, то вiдповiдний рядок game.out порожнiй. Зайвими пропусками при перевірці буде знехтувано.

Приклади

game.ingame.out
1 2 3 4

.
1 2 3


1 2