Третій тур

Розв’язки задач відправляти з 25.10  по 07.11.2010р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

1. Задача TABLE (20 балів)

Ім’я вхідного файлу: TABLE.DAT

Ім’я вихідного файлу: TABLE.SOL

Максимальний час роботи на одному тесті: 2с

В прямокутній таблиці, що складається з M рядків та N стовпчиків, можна за один крок рухатись тільки:

- на одну клітинку вниз;

- через одну клітинку вниз;

- на одну клітинку вправо;

- через одну клітинку вправо.

Необхідно написати програму для знаходження кількості всіх можливих варіантів руху з лівого верхнього кутка таблиці в правий нижній куток.

Формат вхідних даних.

Єдиний рядок вхідного файлу TABLE.DAT містить два натуральні числа M та N (1<=M,N<=1000). Числа між собою розділені пробілами.

Формат вихідних даних.

Єдиний рядок вихідного файлу TABLE.SOL повинен містити одне натуральне число – кількість всіх можливих варіантів руху.

Приклад.

TABLE.DAT:

3 2

TABLE.SOL:

5

2. Задача ROUTES (100 балів)

Ім’я вхідного файлу: ROUTES.dat

Ім’я вихідного файлу: ROUTES.sol

Максимальний час роботи на одному тесті: 5 с.

Один палкий футбольний вболівальник хоче підтримати свою улюблену команду, яка має грати у виїзному матчі, в місті, що знаходиться досить далеко від дому. Щоб потрапити до місця призначення, йому, можливо, прийдеться прямувати через інші населенні пункти. Тому вболівальник заздалегідь дізнався розклад щоденного руху транспорту в кожному з населених пунктів, а також вартість кожного рейсу. Він пронумерував всі населенні пункти від 1 (рідне місто) до N (місто проведення матчу) та виписав розклад в вигляді таблиці, кожен рядок якої мав вигляд

Nвідпр. Nпризн. Tвідпр. Tприб. V,

де Nвідпр. – номер пункту відправлення, Nпризн. – номер пункту призначення, Tвідпр. – час відправлення, Tприб. – час прибуття, V – вартість проїзду.

Матч відбудеться в суботу о 19:00, але так як вболівальник у будні працює до 19:00, він може виїхати зі свого міста не раніше, ніж в п’ятницю, о 19:01.

Необхідно написати програму для знаходження найменшої вартості проїзду для вболівальника, за умови, що він вчасно потрапляє на матч. Якщо ж це неможливо то необхідно вивести повідомлення “impossible”.

Формат вхідних даних.

Перший рядок вхідного файлу ROUTES.dat містить одне натуральне число N (1<=N<=100). Решта рядків – розклад руху транспорту в описаному вище форматі, причому величини часу задаються у вигляді h:m, де h – приймає одне із значень від 0 до 23, а m – від 00 до 59; вартість проїзду задається дійсними числами з двома знаками після коми, такими, що будь-яка сумарна вартість проїзду не перевищує 1000,00. Кількість рейсів з кожного населеного пункту не перевищує 100.

Всі числа між собою розділені пробілами.

Формат вихідних даних.

Єдиний рядок вихідного файлу ROUTES.SOL має містити одне дійсне число з двома знаками після коми – найменшу вартість проїзду або рядок “impossible”.

Примітка.

1. Тривалість кожного рейсу із розкладу менше 24год.

2. Вважається що час на пересадку між рейсами та час, затрачений від місця прибуття до стадіону, рівні 0.

3. При написанні програми не дозволяється використовувати змінні спеціалізованих типів дати та часу.

Приклад.

ROUTES.DAT

4

1 4 16:30 18:59 15.20

1 2 20:00 1:58 3.40

1 3 19:01 10:30 1.50

2 4 2:20 16:50 5.20

2 4 2:50 19:01 4.40

3 4 11:20 17:20 8.20

ROUTES.SOL

8.60

ROUTES.DAT

2

1 2 12:15 2:20 11.60

1 2 6:00 19:01 10.48

ROUTES.SOL

impossible

Умови завдань в форматі МS Word скачати