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


Третій тур
27.11.2006 - 07.12.2006

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

У вищій лізі

- Попик Андрій Васильович, викладач Хмельницького національного університету

У першій лізі - Вапнічний Сергій Дмитрович, вчитель гімназії м.Старокостянтинова

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

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

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

 

 

Вища ліга

Розв'язки приймаються за адресою popyk@ukr.net до 7 грудня 2006 року включно.
Копію: tur3@oiuv.infocom.khmelnitskiy.ua
Тема листа: ZOI_2006

Задача 1. Метеоритний дощ.

   Вчені астрономи, повідомили уряд, що рівно через T секунд на планеті Олімпіада почнеться метеоритний дощ. Уряд планети терміново почав евакуацію людей і важливого обладнання - телескопічних установок.
   Для захисту телескопу його потрібно транспортувати у спеціально відведене місце - сховище. В одному сховищі може вміститися лише один телескоп.
   Необхідно розрахувати максимальну кількість телескопів, які можна встигнути заховати до початку метеоритного дощу.

Вхідні дані (файл METEOR.DAT):
У першому рядку число T - кількість секунд, через яку метеорити впадуть на планету.
У другому рядку число N - кількість телескопів.
У третьому рядку знаходиться 2*N чисел - координати телескопів (x, y).
У четвертому рядку число M - кількість сховищ.
У п'ятому рядку знаходиться 2*M чисел - координати сховищ (x, y).
У шостому рядку число V - швидкість транспортування телескопів.

Обмеження: 0<T<1000000; 0<N<100; 0< M<100; -30000<=x<=30000; -30000<=y<=30000; 0<V<1000
                         T, N, M, x, y - цілі.

Вихідні дані (файл METEOR.SOL):
У єдиний рядок файлу записати максимальну кількість телескопів, що можуть бути сховані до початку падіння метеоритів.

Приклад:

METEOR.DAT
METEOR.SOL
10
4
1 7 3 7 5 7 100 100
2
2 7 4 7
0.1

2


Задача 2. Археологія.

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

Вхідні дані (файл FUND.DAT):
У першому рядку знаходиться число N - кількість фундаментів. (0<N<=3000).
У кожному з наступних N рядків знаходяться координати лівого верхнього і правого нижнього кутів кожного з фундаментів. (координати - цілі числа в межах від 0 до 1000000).

Вихідні дані (файл FUND.SOL):
У вихідний файл записати єдине число - площу покриту фундаментами. Результат записати з трьома знаками після коми.

Приклад:

FUND.DAT
FUND.SOL
3
20 30 40 10
10 40 30 20
23 25 25 15

700.000


Задача 3. Перемикачі.

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

Вхідні дані (файл BOMBA.DAT):
У першому рядку число N. (0<N<=100).
У другому рядку міститься N чисел, що позначають стан кожної лампочки (0 - вимкнена, 1 - ввімкнена).
У третьому рядку міститься число M. (0<M<=100).
В кожному з наступних M рядків міститься число K (кількість лампочок, стан яких змінює даний перемикач) і K чисел - номера відповідних лампочок.

Вихідні дані (файл BOMBA.SOL):
Якщо бомбу знешкодити неможливо, запишіть у вихідний файл "NO" (без лапок).
Якщо можливо врятувати світ, то у перший рядок запишіть "YES" (без лапок), а у другий рядок запишіть номера перемикачів які необхідно задіяти.

BOMBA.DAT
BOMBA.SOL
5
0 1 1 0 1
4
3 2 3 4
3 1 4 5
2 4 5
2 2 4

YES
1 3


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

Кому: popyk@ukr.net
Копія: tur3@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач третього туру.
Учасник вищої ліги з кодом 005.
(Не можна підписувати листи прізвищами)
Вкладка: файли U005T3Z1.PAS, U005T3Z2.PAS, U005T3Z3.PAS                                 на початок


Перша ліга


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

Задача 1. Бірка.

   У короля Лапландії є в наявності різнокольорові стрічки (всього М різних кольорів). Він замислився (і таке буває) чи вистачить йому цих стрічок, щоб однозначно позначити воїнів королівської гвардії.    Допоможіть королю задовольнити цю забаганку. Бірка, яку отримує воїн, містить по одній смужці всіх кольорів, а порядок слідування кольорів у кожного з воїнів – унікальний.

Обмеження: 2<=M<=8; кольори позначені символами латинського алфавіту.

Вхідний файл: birka.in
У єдиному рядку якого, записаний рядок, кожний з М символів якого позначає колір однієї стрічки.

Вихідний файл : birka.out
У перший рядок записати, число яке визначає, яку кількість воїнів можна однозначно позначити, а далі у кожний рядок вихідного файлу записати по одній позначці.

Приклад:

birka.in
birka.out
IOX

6
XOI
OIX
IXO
XIO
OXI
IOX


Задача 2. Покер.

   Задано п’ять цілих чисел. Якщо:

Обмеження: числа не перевищують 100 .

Вхідний файл: poker.in
В єдиному рядку записані п’ять чисел, відокремлені пропусками.

Вихідний файл: poker.out
Вивести один рядок – результат аналізу.

Приклад 1.

poker.in
poker.out
1 3 9 3 2

One Pair

Приклад 2.

poker.in
poker.out
1 5 5 4 4

Two Pairs

Приклад 3.

poker.in
poker.out
1 5 2 4 3

Straight


Задача 3. Листівка та конверт.

   Задані розміри прямокутних листівки та конверта. Потрібно визначити чи поміститься листівка у конверті.

Обмеження: розміри листівки та конверта – цілі додатні числа, які не більші за 100.

Вхідний файл: postcard.in
У першому рядку записані розміри листівки, у другому розміри конверта (в обох випадках відокремлені пропусками).

Вихідний файл: postcard.out
Якщо листівку можна помістити у конверті, то вивести “Possible” , якщо ні – то “Impossible

Приклад 1.

postcard.in
postcard.out
1 10
9 9

Possible

Приклад 2.

postcard.in
postcard.out
9 9
9 9

Impossible


Примітка.

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

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