1. Таксомотор
У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на
першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд 1 до деякого натурального n.
Завдання
Створiть програму tax.*, яка визначить:
час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту;
найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Вхідні дані
Перший рядок файла tax.in м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д початку доби на вказану зупинку таксомотора, що їде j-тим машрутом. Вважається, що на кожнiй зупинцi кожний автобус стоїть рiвно хвилину, пiд час якої можна сiсти на нього або зiйти з нього;
третє (невiд'ємне цiле) число — вартiсть проїзду вiд попередньої зупинки (0 для першої зупинки кожного маршруту, додатне для всiх наступних зупинок).
Загальна кiлькiсть ланок всiх маршрутiв не перевищує 7800.
Вихідні дані
Перший рядок файлу tax.out має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок файлу tax.out має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за 654321.
Приклад
| tax.in | tax.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. Гра «Ряд фішок»
Скiнченну кiлькiсть фiшок розташовано в ряд i вiдповiдним чином занумеровано послiдовними натуральними числами, починаючи з 1. Два гравцi по черзi забирають довiльнi одну або двi фiшки, розташованi поруч (номери яких вiдрiзняються на 1). Переможцем вважають того, хто:
(1) зробить останнiй хiд;
(2) примусить суперника зробити останнiй хiд.
Завдання
Створiть програму game.*, яка для довiльного варiанту гри (1) чи (2) i довiльної позицiї гри визначає всi виграшнi ходи — такi ходи, що ґарантують виграш (за умови правильного продовження гри зi свого боку) незалежно вiд ходiв суперника.
Вхідні дані
Файл game.in мiстить у вказаному порядку:
Вихідні дані
Перший i другий рядки файлу game.out мають мiстити в порядку зростання номери фiшок, забравши якi по однiй або разом з наступною по двi вiдповiдно гравець робить виграшний хiд з позицiї, заданої вхiдними даними. Якщо таких ходiв немає, то вiдповiдний рядок game.out порожнiй. Кожний непорожнiй рядок закiнчується одним пропуском i ознакою кiнця рядка.
Приклади
| game.in | game.out |
|---|---|
| 1 1 2 3 4 | 2 |
| 2 1 2 3 4 | . |
| 1 1 2 3 | 2 |
| 2 1 2 3 | 1 2 |
| 1 2 3 4 6 7 8 9 | 6 7 8 9 2 3 |
3. Календар
Завдання
Встановіть день тижня дати одного року за відомим днем тижня іншої дати цього самого року.
Вхідні дані
Кожний рядок вхiдного файлу calendar.in містить у вказаному порядку 6 чисел:
Вихідні дані
Відповідний рядок вихідного файлу calendar.out містить лише одне натуральне число — номер дня тижня другої дати.
Приклад
| calendar.in | calendar.out |
|---|---|
|
365 1 1 1 3 1 366 7 18 4 21 1 |
3 3 |
Архів прикладів вхідних і вихідних файлів, згаданих в умовах задач, і відкомпільовану програму перевірки правильної взаємодії з системою тестування можна завантажити, натиснувши тут. Для розпакування достатньо змінити розширення на exe та запустити файл на виконання.