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


Четвертий тур
11.12.2006 - 21.12.2006

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

У вищій лізі

- Мельник Валентин Іванович, вчитель ліцею інформаційних технологій м.Олександрія Кіровоградської області

У першій лізі - Зубик Віталій Віталійович, вчитель Летавського ЗНЗ Чемеровецького району

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

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

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

 

 

Вища ліга

Розв'язки приймаються за адресою mvi_7@rambler.ru до 21 грудня 2006 року включно.

Копію надіслати на адресу: tur4@oiuv.infocom.khmelnitskiy.ua

В темі листа слід вказати: ZOI_2006.

Завдання 1. Проблема королів (20 балів)

   На шаховій дошці розміром N на M (3<=N,M<=30) стоять два одиноких королі. Наші королі незвичайні шахові, а загадкові і тому рухаються одночасно за заданою для кожного програмою. Але початкове положення кожного короля не є фіксованим і вони не співпадають.
   Напишіть програму, яка для кожної клітинки поля визначає кількість розміщень другого короля, для випадку коли вони б’ють один одного, якщо перший знаходиться в даній клітинці, жоден з королів не може залишати межі поля.
   Будемо вважати, що королі б’ють один одного, якщо в деякий момент часу вони потрапили на одну клітинку. Після того, як королі побили один одного, їхній рух призупиняється.

   Формат вхідних даних: текстовий файл KINGS.IN містить три рядки: у першому записані два цілих числа N та M – розміри шахової дошки; у другому програма - послідовність ходів першого короля; у третьому програма для другого короля.
   Оскільки королі загадкові, то програма містить не більше 5 команд, кожна з яких це символ, що вказує переміщення на одну з 8 сусідніх клітинок:
U – на одну клітинку вгору;
E – на одну клітинку вверх-вправо;
R – на одну клітинку вправо;
F – на одну клітинку вниз-вправо;
D – на одну клітинку вниз;
G – на одну клітинку вниз-вліво;
L – на одну клітинку вліво;
H – на одну клітинку влiво-вверх.

   Формат вихідних даних: текстовий файл KINGS.OUT має містити N рядків по М чисел у кожному. Кожне число – це відповідь на поставлену задачу для даної клітинки. Якщо для даної клітинки послідовність ходів першого короля завжди призводить до виходу за межі дошки, то вивести -1.

Приклад введення і виведення:

KINGS.IN

KINGS.OUT

3 3
DDR
GDD

1 1 -1
1 1 -1
-1 -1 -1


Завдання 2 . Проблема «Синіх» та «Помаранчевих» (30 балів)

   На території деякої держави ідуть військові навчальні маневри між двома сторонами: «Синіми» і «Помаранчевими». Особливості ландшафту і складні кліматичні умови вимагають підрозділи обох сторін розташовуватись тільки на території деяких населених пунктів. Загальна кількість населених пунктів у державі рівна N.
   Тактика ведення бойових дій «Помаранчевих» розрахована на нанесення супротивнику швидких і раптових ударів, що можливо лише у тому випадку, якщо у операціях задіяні моторизовані частини, а їхнє пересування відбувається тільки по дорогах.
   Розмаїтість використовуваної бойової техніки призводить до того, що час пересування різних бойових частин із одного пункту до іншого різний, і визначається величиною Vj - швидкістю руху підрозділів військової частини розквартированої у j-му населеному пункті.
   Використовуючи величезну перевагу у техніці, «Помаранчеві» планують організувати нічний наліт на бази супротивника і повністю їх розгромити. Всі військові підрозділи «Помаранчевих» приступають до виконання операції одночасно. Якщо бойова частина «Помаранчевих» вривається у населений пункт, занятий «Синіми», то враховуючи фактор раптовості, їм вдається повністю розгромити це угрупування.
   Блискучому проведенню цієї операції завадило те, що через деякий час T після початку операції «Синіми» було здійснено радіоперехоплення повідомлення про операцію, що розпочалася. Після радіоперехоплення угрупування «Синіх» миттєво розсіюються в околишніх горах і залишаються непошкодженими.
   Виясніть, яку кількість угрупувань супротивника і в яких населених пунктах «Помаранчевим» все-таки вдасться розгромити «Синіх».
   Передбачено, що у початковий момент часу угрупування «Помаранчевих» і «Синіх» не можуть знаходитись у одному і тому ж населеному пункті. Якщо сигнал тривоги надходить у той момент, коли бойова частина «Помаранчевих» тільки вривається у населений пункт, зайнятий «Синіми», то, використовуючи чудове знання місцевості, «Синім» все-таки вдається сховатися в горах. Величезна перевага у техніці і живій силі дозволяє бойовим частинам «Помаранчевих» організувати із кожної частини довільну кількість експедицій для розгрому «Синіх». Ніщо не заважає одній експедиції за час проведення операції знищити кілька угруповань.

   Формат вхідних даних: вхідні дані задачі записані у файлі victory.in. У першому рядку цього файлу записані два числа: N – кількість населених пунктів (1<=N<=200) і K – кількість доріг, що з’єднують ці населені пункти (0<=K<=1000). Дороги ніде не перетинаються. У наступних K рядках файлу міститься схема доріг. У кожному рядку записано два натуральних числа i та j і одне додатне дійсне число Lij, яке означає, що між населеними пунктами i та j існує дорога довжиною Lij кілометрів (Lij<1000). Далі описується розміщення бойових частин сторін, що воюють. Наступний рядок файлу містить число М1 – кількість бойових частин «Помаранчевих». У наступних М1 рядках записано по два числа: перше – ціле число j – номер населеного пункту, у якому розміщується військова частина; друге – дійсне невід’ємне число Vj – швидкість руху бойових колон цієї частини у кілометрах за годину (Vj<110). Далі у окремому рядку файлу записано число М2 – кількість бойових угруповань «Синіх», за яким записані М2 чисел – номера населених пунктів, де розташовані ці угруповання. У останньому рядку файлу записане одне додатне дійсне число Т, виміряне у годинах (Т<24). Всі числа розділені пропусками.

   Формат вихідних даних: у перший рядок файлу victory.out виведіть кількість розгромлених угруповань, а у другий – номера населених пунктів (у порядку зростання), у яких ці угруповання базувались.

Приклад введення і виведення:

victory.in

victory.out

8 7
1 2 80
2 4 25
4 5 10
6 2 5
2 3 40
7 6 10
8 7 15
2
1 50
6 20
4 4 5 3 8
2.0

2
4 8


Завдання 3. Проблема «множення» (50 балів)

   У гру «Множення» грають з рядом карт, кожна з яких містить одне додатне ціле число. За один хід гравець забирає одну карту з ряду і отримує певне число балів, рівне добутку числа на забраній карті і чисел на картах, що лежать безпосередньо зліва і справа від неї. Не дозволяється прибирати першу і останню карти ряду. Після останнього ходу у ряду залишаються тільки дві карти.
   Мета гри - прибрати карти у такому порядку, щоб мінімізувати загальну кількість набраних балів.
   Наприклад, якщо карти містять числа 10, 1, 50, 20 і 5, гравець може взяти карту з числом 1, потім 20 і 50, отримуючи бали
10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

   Якби би він взяв карти у зворотному порядку, тобто 50, потім 20, потім 1, кількість набраних балів була б такою:
1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

   Формат вхідних даних: у першому рядку файлу mpuzzle.in знаходиться одне число – кількість карт N, у другому - розділені пропусками N чисел на картах.

Обмеження: 3<=N<=100, числа на картах цілі від 1 до 100.

   Формат вхідних даних: виведіть у файл mpuzzle.out одне ціле число - мінімально можливе число балів.

Приклад введення і виведення:

mpuzzle.in

mpuzzle.out

6
10 1 50 50 20 5

3650


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

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


Перша ліга

Розв'язки приймаються і аналізуються за адресою letavasc@cm.km.ua до 21.12.2006 включно.

Копія на адресу: tur4@oiuv.infocom.khmelnitskiy.ua

Тема листа: ZOI_2006.

Питання, щодо умов задач приймаються за адресою letavasc@cm.km.ua до 21 грудня 2006 включно.

Кролики, это не только ценный мех…
В. Моисеенко, В. Данилец

Задача 1. «Кролики» (40 балів)

   Є пара кроликів. Пара починає щомісяця народжувати нову пару на третій місяць життя. Одна пара кроликів живе k місяців. Скільки кроликів буде через n місяців?

Технічні умови. У стандартному вхідному потоці міститься два цілі числа k і n (3<=k<=n<=30). У стандартний вихідний потік вивести єдине ціле число – кількість кроликів через n місяців.
Вхідні дані
6 6
Вихідні дані
14


Задача 2. «Кролики-2» (30 балів)

   Земляни знайшли планету, придатну для життя і відправили космічний корабель з одним кроликом щоб переконатися у придатності для життя клімату планети. Кролику сподобався клімат і уже через місяць він привів ще одного (на цій планеті для цього достатньо одного кролика). Далі кролики почали розмножуватися з такою ж швидкістю – кожен кролик через місяць приводив ще одного. Але, розмноження кроликів почав контролювати монстр – корінний житель цієї планети. Як тільки на початку якогось місяця кроликів ставало більше ніж k, він поїдав k кроликів.
   Земляни повернулися на планету через n місяців. Скільки кроликів вони нарахували?

Технічні умови. У стандартному вхідному потоці міститься два цілі числа n і k (0<=n<=20, 1<=k<=1000), у стандартний вихідний потік вивести єдине ціле число – кількість кроликів через n місяців.
Вхідні дані
5 10
Вихідні дані
12

Пояснення. На кінець першого місяця кроликів стало 2, другого – 4… На початок 5 місяця їх було 16 і монстр з’їв 10. Отже, кроликів залишилося 6 і на кінець цього місяця добавилося ще 6. Маємо 12 через 5 місяців.


Задача 3. «Кролики-3» (30 балів)

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

 

 

 

3

 

 

 

 

 

 

 

4

 

 

 

5

 

  

 

  

 

2

 

 

 

Технічні умови. У вхідному файлі rabbits.dat у першому рядку знаходиться три цілих числа: N (1<N<100) – розмір квадратної огорожі; R, C – рядок і стовпець умовної клітинки огорожі, де знаходиться кролик. У наступних N рядка записано по N чисел: 0 вказує на відсутність нори, інше число – на нору з переходом у клітку з таким номером. У вихідний файл rabbits.sol у випадку, коли кролик поїсть моркви, вивести “YES” у першому рядку та кількість нірок у другому. При відсутності шляху вивести в першому рядку “NO”, а в другому – номер останньої клітки, до якої може пройти кролик.
Вхідні дані
5 1 1
0 0 0 3 0
0 0 0 0 0
0 4 0 0 0
5 0 0 0 0
0 2 0 0 0

Вихідні дані
YES
3


Примітка.

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

Кому: letavasc@cm.km.ua
Копія: tur4@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач четвертого туру.
Учасник першої ліги з кодом 505.
(Не можна підписувати листи прізвищами)
Вкладка: файли U505T4Z1.PAS, U505T4Z2.PAS, U505T4Z3.PAS                                 на початок