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 |
NE 7 |
Приклад 2.
| owl.dat | owl.sol |
|---|---|
3 5 |
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 |
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 |
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 |
Примітки:
1 . Програми називати z5.pas, z6.pas, z7.pas, z8.pas, де pas – розширення мови програмування Паскаль.
2. У випадку утруднень роботи з кирилицею на робочому місці, використовуйте для відлагодження програми латинь.