Годинник | |
|
2005 рік
|
| |
|
XVIII Всеукраїнська олімпіада з інформатики
|
XVIII Всеукраїнська олімпіада з інформатики
Перший тур
Сірники (100 балів)
Яка мінімальна кількість сірників потрібна для того, щоб викласти на площині N квадратів зі стороною в один сірник?
Сірники не можна ламати та класти один на одний.
Вершинами квадратів повинні бути точки, де сходяться кінці сірників, а сторонами - самі сірники.
Завдання
Напишіть програму MATCHES, що за кількістю квадратів N, які необхідно скласти, знаходить мінімальну необхідну для цього кількість сірників.
Вхідні дані
Єдиний рядок вхідного файлу MATCHES.DAT містить одне ціле число N (1<=N<=109).
Вихідні дані
Єдиний рядок вихідного файлу MATCHES.SOL має містити одне ціле число - мінімальну кількість сірників потрібних для складання заданої кількості квадратів.
Приклад вхідних та вихідних даних
| MATCHES.DAT | MATCHES.SOL |
| 4 | 12 |
Альтернативні шляхи (100 балів)
Задано прямокутну таблицю розміром M рядків на N стовпчиків. У кожній клітинці записане натуральне число, не більше 200. Мандрівник має пройти по цій таблиці з лівого верхнього кута у правий нижній, на кожному кроці переміщуючись або на 1 клітинку праворуч, або на 1 клітинку вниз. Очевидно, таких шляхів багато. Для кожного шляху можна порахувати суму чисел у пройдених клітинках. Серед цих сум, очевидно, є максимальна.
Будемо поблажливими до Мандрівника, і вважатимемо "гарними" не лише шляхи, на котрих в точності досягається максимально можлива сума, а ще й шляхи, сума котрих відрізняється від максимальної не більше ніж на K.
Кількість "гарних" шляхів гарантовано не перевищує 109.
Завдання
Напишіть програму GOODWAYS, що знаходить значення максимально можливої суми та кількість "гарних" шляхів.
Вхідні дані
Перший рядок вхідного файлу GOODWAYS.DAT містить три цілих числа M (2<=M<=200), N (2<=N<=200) та K (0<=K<=200). Кожен з наступних M рядків містить N чисел, записаних у відповідних клітинках.
Вихідні дані
Перший рядок вихідного файлу GOODWAYS.SOL має містити максимальну можливу суму; другий рядок - кількість маршрутів, сума чисел котрих відрізняється від максимальної не більш ніж на K.
Приклад вхідних та вихідних даних
| GOODWAYS.DAT | GOODWAYS.SOL |
2 3 3
1 9 7
2 5 3 | 20
2 |
Театр (100 балів)
У Театрі збираються поставити грандіозну п'єсу з двох актів, в якій освітлення має велике значення. Сцена театру має форму опуклого многокутника, заданого вершинами у декартовій прямокутній системі координат. Над сценою знаходиться прожектор, що може переміщуватися над нею довільним чином. Знаходячись у деякій точці, прожектор освітлює круглу область з центром у цій точці та радіусом R.
У першому акті на сцені лежать квадратні килими розміром HxH, сторони яких паралельні осям координат. Килими можуть частково виходити за межі сцени. Розглянемо фігуру, що складається з усіх точок, знаходячись в яких, прожектор не освітлює жоден з килимів та не освітлює територію поза сценою. Позначимо її площу як S1.
Перед другим актом килими прибирають зі сцени. Розглянемо фігуру, яка складається з усіх точок, знаходячись в яких, прожектор не освітлює територію поза сценою. Її площу позначимо як S2.
Завдання
За наданими вхідними файлами, кожен з яких описує сцену та розташування на ній килимів у першому акті, створіть відповідні їм вихідні файли, що містять площі S1 та S2 описаних вище фігур.
Вхідні дані
На вашому диску в каталозі DATA містяться 10 файлів, що мають назви THEATER.D01, THEATER.D02, … , THEATER.D10, такого формату.
У першому рядку задано числа R, H, N, M. Де R - радіус області, яку освітлює прожектор. H - довжина сторони квадрата, що представляє килим. N - кількість вершин опуклого многокутника, що задає сцену. M - кількість килимів. У другому рядку знаходяться N пар чисел - координати вершин многокутника у порядку обходу (за або проти годинникової стрілки). У третьому рядку знаходяться M пар чисел - координати центрів килимів.
Вихідні дані
Створіть 10 вихідних файлів THEATER.S01, THEATER.S02, … , THEATER.S10 у вашому каталозі на дискеті. Ці файли повинні містити відповіді для відповідних вхідних файлів.
Кожен файл повинен містити два числа - цілі частини площ S1 та S2. Вам не потрібно здавати програму! Бали будуть нараховуватися за файли з правильними відповідями.
Приклад вхідних і вихідних файлів
| THEATER.D00 | THEATER.S00 |
0.5 2 4 1
1 1 5 1 5 4 1
4
3 4 | 3 6 |
Другий тур
Рахунок гри (100 балів)
Задано квадратну дошку розміром NxN. Відомо, що на ній грали в інтелектуальну гру, внаслідок чого клітинки виявилися зафарбованими у білий, чорний та зелений кольори. Розфарбування клітинок може бути різним (адже це інтелектуальна гра!), але всі клітинки самого верхнього рядка білі, а самого нижнього - чорні.
Щоб з'ясувати переможця, потрібно порахувати кількості клітинок у білій області та чорній області. Біла область - це якнайбільша (за кількістю клітинок) частина квадрата, котра обмежується згори верхньою стороною квадрата, з інших боків - неперервною межею, що проходить лише через білі клітинки і жодна клітинка не зустрічається більше одного разу. Біла межа являє собою послідовність білих сусідніх клітинок (сусідні клітинки мають спільну сторону). Кінцями цієї межі повинні бути ліва верхня та права верхня клітинки квадрата.
Означення чорної області аналогічне: вона обмежена знизу нижньою стороною квадрата, з інших боків - чорною межею, що проходить лише через чорні клітинки, а кінцями цієї межі є ліва нижня та права нижня клітинки квадрата.
Завдання
Напишіть програму SCORE, що за розфарбуванням квадрата знаходитиме кількості клітинок у білій області та чорній області.
Вхідні дані
Перший рядок вхідного файлу SCORE.DAT містить єдине ціле число N - розмір квадрата (5<=N<=250). Кожен з наступних N рядків містить по N символів "G", "W" або "B" (записаних без пропусків), котрі позначають зелений, білий та чорний кольори відповідно.
Вихідні дані
Перший рядок вихідного файлу SCORE.SOL має містити кількість клітинок у білій області, другий рядок - у чорній області.
 |
Приклад вхідних та вихідних даних
| SCORE.DAT | SCORE.SOL |
7
WWWWWWW
WGWWBWG
WWWWGWW
BBGWWWB
GWBBWGB
BBBBGBB
BBBBBBB | 2215 |
|
Вигляд білої та чорної областей для прикладу з умови представлено на рисунку.
Доміно (100 балів)
Набір доміно складається з прямокутних кісточок, кожна з яких розділена на дві половинки лінією, паралельною коротшій стороні. На кожній з половинок намальовані крапки, кількість яких дорівнює числу від 0 до M включно. На кісточках повного набору доміно позначені всі можливі різні пари чисел, наприклад, якщо M дорівнює 3, то повний набор містить 10 кісточок: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
З кісточок можна викладати ланцюги, з'єднуючи пари кісточок короткими сторонами, якщо кількості крапок на сусідніх з місцем з'єднання половинках кісточок рівні.
Деякі кісточки вилучили з повного набору. Треба визначити, яку мінімальну кількість ланцюгів потрібно викласти з кісточок, котрі залишились у наборі, щоб кожна з них належала рівно до одного ланцюга.
Завдання
Напишіть програму DOMINO, яка за інформацією про набір доміно повинна відповісти, яку мінімальну кількість ланцюгів треба викласти.
Вхідні дані
У першому рядку вхідного файлу DOMINO.DAT міститься одне ціле число M (0<=M<=100), яке відповідає максимально можливій кількості крапок на половинці кісточки. У другому рядку записано одне ціле число N, яке дорівнює кількості кісточок, що були вилучені з повного набору. Кожний і-й з наступних N рядків містить по два числа, Ai та Bi. Це кількості крапок на половинках i-ї кісточки, що була вилучена.
Вихідні дані
Єдиний рядок вихідного файлу DOMINO.SOL має містити одне ціле число L - мінімальну кількість ланцюгів.
Приклад вхідних та вихідних даних
| DOMINO.DAT | DOMINO.SOL |
7
2
7 5
3 4
| 2 |
Скелі (100 балів)
На планеті Олімпія робітники будують нову дамбу. Частина площини, де проводяться будівельні роботи, має вигляд прямокутника розміром 1 x L метрів, на якому введено координати, як показано на рисунку.
Для підняття ландшафту використовуються спеціально розроблені магічні імпульсатори. Якщо магічний імпульсатор з силою H поставити в точку з X-координатою p, то в кожній точці q відрізку [p-H;p] на вісі X рельєф піднімається на q-p+H метрів по всій його ширині (тобто для довільного Z від 0 до 1), а в кожній точці q відрізка [p;p+H] рельєф піднімається на H+p-q метрів по всій його ширині, в інших точках ландшафт залишається незмінним (див. рисунок).
Під час будівництва робітники час від часу цікавляться об'ємом дамби, що знаходиться вище деякого прямокутника.
Завдання
Напишіть програму ROCKS, що допоможе робітникам у їхніх обрахунках.
Вхідні дані
В першому рядку вхідного файлу ROCKS.DAT містяться два цілих числа: N - кількість операцій, що будуть виконувати робітники (1<=N<=100000), та L - довжина прямокутника (1<=L<=100000).
В наступних N рядках містяться описи операцій: перше число рядка - номер операції, де "1" означає, що робітники збираються поставити магічний імпульсатор, "2" - робітники бажають дізнатися деякий об'єм. Якщо операція має код "1", то далі йдуть два цілих числа p та H (0<=p<=L; 1<=H<=L), тобто імпульсатор сили H ставлять на позицію p (на вісі X). Якщо операція має код "2", то далі йдуть два цілих числа A та B (0<=A
Вихідні дані
Створіть вихідний файл ROCKS.SOL у якому для кожної операції, вказаної у вхідному файлі, виведіть рядок з наступною інформацією.
Якщо операція є "1", то виведіть число "-1" без лапок. Якщо операція є "2", то виведіть число, яке дорівнює об'єму частини дамби, що знаходиться над прямокутником від A до B по вісі X, та від 0 до 1 по вісі Z, як це показано на рисунку.
Приклад вхідних та вихідних даних
| ROCKS.DAT | ROCKS.SOL |
2 13
1 7 5
2 5 9
| -116 |
Повний архів олімпіади (~4,5 Mb)
|
|
© Всеукраїнський віртуальний центр олімпіад школярів
"ОЛІМП"
|
| |
| |
