XX обласна олімпіада з інформатики

Хмельницька область
І тур
18 лютого 2006 року


Задача 1. Word

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

Задача 2. Chess

Піхотинець проти вершника! Ніяких шансів для перемоги!? Подивимось. Отже, поле бою – шахова дошка розмірності NxN (4<=N<=100) . На дошці знаходяться кінь та пішак. Ваша задача написати програму, що визначає кількість ходів, які потрібно зробити коневі, щоб побити пішака, який прямує у дамки, або вивести 0, якщо цього він зробити не зможе. Пішак ходить лише на одну клітинку вперед; якщо пішак дійшов у дамки (на перший рядок таблиці) і кінь має черговий хід у цю клітинку, то мрії пішака не здійснилися.

Вхідний файл chess. in містить єдиний рядок у якому знаходяться в такому порядку цілі числа через пропуск: перше число N – розмір дошки, друге – 0 або 1 (1 – перший хід пішака, 0 – перший ходить кінь), далі записані координати коня та пішака.

Вихідний файл chess . out містить єдине число – кількість ходів коня, або 0.

Наприклад:

chess.in

chess.out

4 1 4 1 2 4

0

4 0 4 1 2 4

2

Задача 3. Подарунок для Мудрої Сови

П’ятачок і Вінні-Пух зібрались до Мудрої Сови на день народження. В якості подарунка вирішили назбирати букет польових ромашок. Ромашкове поле задано прямокутною матрицею M x N, в клітинках якої записано кількість ромашок, що ростуть на даному клаптику поля. Будь-який клаптик поля містить хоча б одну ромашку.

П’ятачок і Вінні-Пух вміють ходити лише по горизонталі і вертикалі, при цьому, зробивши хід на схід, уже не можна буде потім ходити на захід і навпаки, а також, зробивши хід на північ не можна буде ходити на південь і навпаки. В початковий момент гості Мудрої Сови знаходяться в центральній клітинці поля.

Напишіть програму, що допоможе вказати напрямок руху: NW – північний захід, NE   – північний схід, SW- південний захід, SE – південний схід. Та визначте при цьому максимально можливу кількість ромашок у букеті.

Технічні умови:

У першому рядку вхідного текстового файлу owl.dat записано через пропуск два цілих непарних числа: M і N. (2<M,N<100).

В наступних M рядках записано по N чисел у кожному розділених пропуском. Кожне з чисел не перевищує 10000.

Ваша програма повинна вивести у файл owl.sol напрямок руху у вигляді: NW – північний захід, NE – північний схід, SW- південний захід, SE – південний схід. Та через пропуск у відповідному рядку кількість ромашок. Якщо таких напрямків буде більше одного, то вивести всі від NW за годинниковою стрілкою.

Приклад 1.

owl.dat owl.sol

3 3
1 2 3
3 2 1
1 1 1

NE 7

Приклад 2.

owl.dat owl.sol

3 5
1 2 1 2 1
3 2 1 2 3
1 1 3 1 1

NW 7
NE 7
SE 7
SW 7

Задача 4 . Tap_Lap

Будівельна фірма «Тяп-Ляп» приймає замовлення на обробку стін внутрішніх приміщень (вирівнювання, штукатурка, фарбування і т.п.). Для розрахунку вартості робіт необхідно знати площу стін. Вам необхідно скласти програму, яка по заданому плану приміщення розраховує площу внутрішніх стін. План є прямокутною сіткою, на якій задано розташування стін. Ширина однієї клітини складає D метрів, висота стель скрізь однакова і дорівнює L метрів.

Вхідні дані:

В першому рядку вхідного потоку міститься два дійсні числа D, L. В другому рядку – два цілі числа N, M (довжина і ширина приміщення, задана в кількості клітин, 1<=N, M<=100). В наступних N рядках містяться по M чисел, кожне з яких дорівнює 0 (клітина не належить стіні) або 1 (клітина належить стіні). Всі числа розділяються між собою пропуском.

Вихідні дані:

У вихідний потік необхідно вивести одне число – обчислену площу стін, з точністю до двох знаків після коми.

Наприклад (для схеми, наведеної в умові):

Input

Output

1 3
12 14
0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 1 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 1 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 1 0 1 1 0 0 0 0 1
1 0 0 0 0 1 0 0 1 0 0 0 0 1
1 0 1 0 0 1 0 0 1 1 1 1 1 1
1 0 1 1 1 1 0 0 1 0 0 0 0 1
1 0 1 0 0 1 0 0 0 0 0 0 0 1
1 0 1 0 0 1 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 0

312.00

Примітка. Програми називати z1.pas, z2.pas, z3.pas, z4.pas, де pas – розширення мови програмування Паскаль.


IІ тур
19 лютого 2006 року


Задача 5 . Знайомства (GROUP)

На олімпіаду з інформатики приїхало N учасників (1<=N<=200). Деякі з них вже знайомі між собою. Вам необхідно написати програму, яка визначає, скільки вийде груп знайомих, після того, як учасники перезнайомляться між собою опосередковано (через спільного знайомого).

Вхідні дані:

У вхідному потоці в першому рядку міститься число N . Далі, в N рядках задані цілі числа, розділені пропусками, які позначають номери учасників, з якими знайомий цей учень. Якщо учасник ні з ким не знайомий, то в рядку міститься значення 0.

Вихідні дані:

У вихідний потік необхідно вивести одне число – кількість груп.

Наприклад:

Input

Output

6
5 3
4
1
2
1
0

3

Задача 6 . Золоте дерево (GOLDTREE)

Як відомо, дурнуватий Буратіно за порадою кота Базіліо і лисиці Аліси рівно опівночі на Полі чудес в Країні дурнів посадив «золотий». В перший день з «золотого» виросте стовбур одиничної довжини. За кожний наступний день кожна гілка чарівного дерева, включаючи стовбур, виростає в тому ж напрямі ще на одну одиницю довжини. При цьому, в кінці кожної гілки зав'язується одна нова брунька. Наступного дня із зав'язаної бруньки виростають нові гілки одиничної довжини і т.д. По законах казкової ботаніки в повний місяць на гілках, які не молодше K-го і не старше за N-го порядку, з ще не пророслих бруньок замість паростків з'являються золоті плоди. (Порядок гілки визначається її положенням відносно стовбура: стовбур має нульовий порядок, гілки, що ростуть від стовбура – перший порядок, від гілок першого порядку – другий і т.д., див. рис).

Вам необхідно написати програму, яка дозволяє визначити кількість золотих плодів, якщо повний місяць відбудеться через T днів (1<=Т<=28).

Вхідні дані:

Вхідний потік містить три цілі числа T, K і N, розділені між собою пропусками.

Вихідні дані:

У вихідний потік необхідно вивести одне число – кількість золотих плодів.

Наприклад:

Input

Output

3 1 3

3

Задача 7 . Шпигуноманія (AGENT )

Агент Джеймс Бонд передає свої повідомлення в Центр за допомогою електронної пошти. Лист складається з N рядків (1<=N<=50000), довжина яких не перевищує 255 символів. Для того, щоб затрудняти розшифровку повідомлення в лист поміщається «сміття», яке складається з рядків, що повторюються. Кожний рядок, що відноситься до «сміття» повторюється парну кількість разів, і лише один рядок зустрічається в листі тільки один раз (це і є власне повідомлення агента). Вам необхідно написати програму, яка із заданого тексту листа визначить текст повідомлення Джеймса Бонда.

Вхідні дані:

Вхідний потік містить набір рядків листа. Ознакою закінчення листа є символ «#», який стоїть в окремому рядку (даний рядок до тексту листа не відноситься).

Вихідні дані:

У вихідний потік необхідно вивести знайдений рядок повідомлення.

Наприклад:

Input

Output

Куй залізо, не відходячи від каси
Алло шеф, це я - Льолік
Битиму акуратно, але сильно
Битиму акуратно, але сильно
Куй залізо, не відходячи від каси
#

Алло шеф, це я - Льолік

 

Задача 8. Музична колекція (Music)

Школяр Вася зібрав музичну колекцію, яка складається з M улюблених пісень. Щоб слухати пісні, Вася вирішив записати їх на N дисків, кожен з яких може вміщувати не більш ніж P хвилин музики за такими правилами:

1) пісні повинні розташовуватися в порядку зростання номерів, тобто для будь-яких двох дисків усі пісні з одного повинні мати менші номери, ніж пісні з другого;

2) кількість записаних пісень повинна бути максимально можливою.

Знаючи скільки хвилин займає кожна пісня, допоможіть Васі впоратися із поставленим завданням.

Вхідні дані.

В першому рядку файлу music.dat знаходяться числа N, P, M розділені пропуском. (1<=N,P,M<=30).

В наступних M рядках по одному числу: в i-му рядку розмір у хвилинах пісні з номером (i-1). Всі вхідні дані - цілі числа.

Вихідні дані.

В перший рядок файлу music.sol вивести максимальну кількість пісень, яку Вася зможе записати на диски.

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

music.dat

music.sol

2 5 3
2
4
3

2

Примітки:
1 . Програми називати z5.pas, z6.pas, z7.pas, z8.pas, де pas – розширення мови програмування Паскаль.

2. У випадку утруднень роботи з кирилицею на робочому місці, використовуйте для відлагодження програми латинь.