Заочна олімпіада з інформатики
Хмельницька область 2006 - 2007


Другий тур
13.11.2006 - 23.11.2006

Тур проводять:

У вищій лізі - Кухар Андрій Володимирович , викладач Хмельницького національного університету
У першій лізі - Кокорський Сергій Людвигович, вчитель Славутського НВК "Успіх"

 

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

УМОВИ ЗАВДАНЬ

ВИЩА ЛІГА ПЕРША ЛІГА

 

 

Вища ліга

   Розв'язки та запитання щодо умови задач приймаються за адресою kobold@binet.com.ua до 23 листопада 2006 року включно.
   Копію листів необхідно надсилати за адресою tur2@oiuv.infocom.khmelnitskiy.ua.

   Час роботи програми не повинен перевищувати 5 секунд на Celeron 2.4MHz.
   Всі дані вводятся з стандартного потоку введення (з клавіатури). Всі дані виводяться в стандартний потік виводу (на екран). Не виводьте ніяких даних, що не вказані в умові задачі (наприклад запросів "введіть N"), не використовуйте модулі Crt чи conio.


Задача 1. Аеропорт. (50 балів)

   Компанія "Хмельницькі авіалінії" бажає здійснювати пасажирські перевезення на низці рейсів виду Хмельницький -- деяке місто -- Хмельницький. Виліт літака на кожен з рейсів здійснюється щоденно. Для кожного рейсу відома необхідна година виходу літака на рейс та година звільнення літака з рейсу після його повернення в аеропорт міста Хмельницького. Наприклад, Хмельницький -- Одеса -- Хмельницький 15:35 - 18:20, Хмельницький -- Стамбул -- Хмельницький 12:50 -- 17:45. Якщо проміжки часу, необхідні для обслуговування рейсів не перетинаються, то ці рейси може обслуговувати один літак.

Задача. За даним списком рейсів, що визначені часом початку та закінчення обслуговування рейсу, визначити найменшу кількість літаків, яка зможе обслуговувати всі ці рейси. Кількість рейсів не перевищує 1000.

Вхідні дані. В першій стрічці вхідного потоку міститься одне число -- кількість рейсів. В наступних стрічках міститься опис рейсів, по одному в кожній стрічці, у вигляді: час початку - час завершення. Наприклад, 13:20 - 18:10. Значення годин та хвилин завжди містять дві цифри. Значення часу та знак "-" можуть бути відокремлені деякою кількістю пропусків. Вхідні дані гарантовано містять коректне значення годин та хвилин.

Вихідні дані. В першу стрічку вихідного потоку вивести єдине число -- найменшу кількість літаків, що можуть обслуговувати всі дані рейси.

Приклад вхідних даних:

5
03:50 - 09:10
05:15 - 08:45
08:55 - 12:20
10:15 - 15:35
23:10 - 03:30

Приклад вихідних даних, що відповідають вхідним:

2

Задача 2. Центральна точка. (30 балів)

На площині знаходиться n точок з цілими координатами (xi, yi); i = 1..n; n <= 1000; -10000 <= xi, yi <= 10000. Назвемо центральною точкою одну з заданих точок з координатами (xc, yc), таку, що для будь-якої іншої заданої точки (xi, yi) існує точка (xj, yj), така, що xc - xi = xj - xc та yc - yi = yj - yc (тобто точки (xi, yi) та (xj, yj) є симетричними відносно точки (xc, yc)).

Задача. Визначити, чи існує серед заданих точок центральна точка.

Вхідні дані. В першій стрічці вхідного потоку міститься одне число n. В наступних стрічках містяться координати заданих точок, по одній точці в кожній стрічці. Координати точки є парою цілих чисел, що розділені одним або більше пропусками.

Вихідні дані. В першу стрічку вихідного потоку вивести координати центральної точки, розділивши їх одним або більше пропусками. Або вивести один знак "-", якщо у заданих точок не існує центральної точки.

Приклад вхідних даних:

6
0 4
2 6
1 3
2 2
2 6
0 0

Приклад вихідних даних, що відповідають вхідним:

1 3

Задача 3. Послідовність 01. (20 балів)

Визначити скільки існує послідовностей з 0 та 1 довжиною n, в якій не зустрічається двох одиниць підряд. n < 45.

Вхідні дані. В першій стрічці вхідного потоку міститься єдине число n.

Вихідні дані. В першу стрічку вихідного потоку вивести єдине число -- кількість послідовностей довжини n, в яких не зустрічається двох одиниць підряд.

Приклад вхідних даних:

5

Приклад вихідних даних, що відповідають вхідним:

13

Примітка.
Приклад листа другого туру учасника вищої ліги з кодом 005.

Кому: kobold@binet.com.ua
Копія: tur2@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач другого туру.
Учасник вищої ліги з кодом 005.
(Не можна підписувати листи прізвищами)
Вкладка: файли U005T2Z1.PAS, U005T2Z2.PAS, U005T2Z3.PAS                                 на початок

=================================================================================

Перша ліга

Розв'язки приймаються і аналізуються за адресою kokorsky@rambler.ru до 23.11.2006 включно.
Копію: tur2@oiuv.infocom.khmelnitskiy.ua
Тема листа: ZOI_2006

Питання щодо умов задач можна надсилати на kokorsky@rambler.ru до 23.11.2006 включно.

Задача 1. «День Святого Миколая» (40 балів)

   До дня Святого Миколая залишилось трохи більше місяця. Відроджуючи традиції, і задля реклами свого свята, Святий Миколай влаштував змагання з Дідом Морозом, хто заробить більше дитячих усмішок. Звичайно, усмішки діти віддають взамін подарунків. Одного ранку дітки мають гарний настрій і дарують більше усмішок, а іншого ранку їх змушують застеляти ліжко – і усмішок, відповідно, менше, але кожного ранку кількість усмішок за один подарунок не менше 1 і не більше 100. Стартує Святий Миколай вранці з одного подарунка, але кожної ночі він встигає виготовити ще 1 (подарунки можна роздавати лише вранці, а виготовляти лише вночі). Змагання довгострокове і термін його закінчення Святий Миколай залишив в таємниці, повідомивши його (термін) лише своїм друзям, однак зауважив, що змагання не триватимуть довше 2000000 діб. Друзі підготували йому прогноз кількості дитячих усмішок за один подарунок на кожен ранок відповідного періоду. Миколай не зобов’язаний дарувати подарунки щоранку. Допоможіть Святому Миколаю роздати подарунки так, щоб отримати за цей період якнайбільше усмішок.
    Вхідні дані: У текстовому файлі Usmishka.dat знаходиться послідовність цілих чисел, записаних через пропуск – прогноз кількості усмішок, які можна отримати за один подарунок, кожного ранку періоду змагань.
    Вихідні дані: У текстовому файл Usmishka.sol вивести одне ціле число – кількість усмішок, які отримав Святий Миколай за весь період змагання.

Приклад 1:

Usmishka.dat
Usmishka.sol
3 5 2
12

Приклад 2:

Usmishka.dat
Usmishka.sol
2 1 1 1 1
6

Задача 2. «Сніжинки в листопаді» (40 балів)

   В листопаді мороз формує особливі сніжинки: з кристалів, що мають форму відрізків прямої, у вигляді візерунка, що зображений на малюнку. Радіальні кристали послідовно пронумеровані від 0 до 5 і утворюють кути 60 градусів. Кристали, що утворюють вкладені шестикутники, нумеруються від центру сніжинки (сам центр має номер 0) і кріпляться до радіальних кристалів з одиничним кроком.
          .                .
           .              .
            \1           /2
             \__________/
            / \        / \
           /   \______/   \
          /    /\    / \   \
         /    /  \__/   \   \
        /    /  / \/1\  2\  3\
...0___/____/__/__0___\___\___\____3...
       \    \  \  /\  /   /   /
        \    \  \/__\/   /   /
         \    \ /    \  /   /
          \    /______\/   /
           \  /        \  /
            \/__________\/
            /            \
           /5             \4
          .                .
         .                  .

!!!!!!!!!!!!!!!!!!!!!
ДЛЯ ТОГО, ЩОБ ПРИ ПЕРЕГЛЯДІ СХЕМА ВІДОБРАЖАЛАСЬ ПРАВИЛЬНО, ПОТРІБНО ВСТАНОВИТИ ШРИФТ "FIXEDSYS" АБО "Lucida Console"
!!!!!!!!!!!!!!!!!!!!!

   Координати вузла сніжинки задають двома числами (R, N), де R – номер радіального кристалу, а N – номер шестикутника (0 <= N <= 30000). Кожна сніжинка має рівно два особливих – платинових – вузли. Кристалічний чоловічок знаходиться у вузлі з координатами (a, b) і мусить відвідати обидва платинові вузли. Він може рухатись лише вздовж кристалів сніжинки. Написати програму, яка за координатами стартового і двох платинових вузлів визначає довжину найкоротшого шляху кристалічного чоловічка, який він проходить зі свого стартового вузла до одного з платинових, обов’язково проходячи перед цим через інший платиновий вузол.
   Вхідні дані: зі стандартного вхідного потоку вводяться шість чисел по два, відокремлені пропусками, в рядку – координати стартового вузла чоловічка, першого і другого платинових вузлів сніжинки відповідно.
   Вихідні дані: у стандартний вихідний потік вивести одне число – довжину найкоротшого шляху кристалічного чоловічка між цими вузлами.

Приклад:

Вхідні дані:
Вихідні дані:
3 1
1 3
2 2
5

Задача 3. «Таблиця» (20 балів)

   Елементи квадратної таблиці нумеруються таким чином:

j
i
1 2 5 10 ...
4 3 6 11 ...
9 8 7 12 ...
16 15 14 13 ...
... ... ... ... ...

   За заданим k (1<=k<=2116000000) знайти його місце в таблиці i, j. Нумерація рядків і стовпців таблиці починається з одиниці.
   Вхідні дані: зі стандартного вхідного потоку вводиться задане число k.
   Вихідні дані: у стандартний вихідний потік вивести два числа – номери рядка та стовпця таблиці, на перетині яких знаходиться число k.
Приклад:

Вхідні дані:
Вихідні дані:
12
3 4

Примітка.

Приклад листа другого туру учасника першої ліги з кодом 005.

Кому: kokorsky@rambler.ru
Копія: tur2@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач другого туру.
Учасник першої ліги з кодом 505.
(Не можна підписувати листи прізвищами)
Вкладка: файли U505T2Z1.PAS, U505T2Z2.PAS, U505T2Z3.PAS                                 на початок