XVII Всеукраїнська олімпіада з інформатики
Перший тур
Вектори (100 балів)
На площині задано множину точок (x, y), де x та y – цілі, 1≤x≤M, 1≤y≤N. З кожної точки виходить рівно один з наступних векторів: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Кожен вектор сполучає одну цілочисельну то
чку площини з іншою. Наприклад, якщо з точки (2, 5) виходить вектор (1, 1), то він сполучає цю точку з (3, 6), але не навпаки.Послідовність з двох і більше точок площини a1, a2,…, ak назвемо циклом, якщо кожна точка ai сполучена вектором з ai+1 (1≤i≤k-1), та ak сполучена вектором з a1. Цикли вважаються різними, якщо вони відрізняються хоча б однією вершиною.
Завдання. Напишіть програму VECTORS, що за інформацією про вектори, що виходять з точок площини, знаходить кількість різних циклів
Вхідні дані. Перший рядок вхідного файлу VECTORS.DAT містить два цілих числа N (1≤N≤100) та M (1≤M≤100). Кожен з наступних N рядків, містить M пар чисел (тобто, 2×M чисел). Пара x, що знаходиться у рядку y задає вектор у точці (x, y).
Вихідні дані.Єдиний рядок вихідного файлу VECTORS.SOL має містити ціле число – кількість циклів, утворених векторами.
Приклад вхідних та вихідних даних
|
VECTORS.DAT |
VECTORS.SOL |
|
2 4 -1 1 -1 1 -1 0 0 1 1 0 1 0 0 -1 0 -1 |
2 |
Погодні умови (100 балів)
Система рейсів авіакомпанії OlympAirways була спроектована таким чином, щоб з будь-якого аеропорту, що обслуговується авіакомпанією, можна було перелітіти до будь-якого іншого аеропорту, скориставшись, можливо, більше ніж одним рейсом. Кожен рейс сполучає два аеропорти, та виконується у обидва боки. Існує проблема, що деякі рейси певний час можуть не виконуватись через погані погодні умови. Таким чином, ймовірно, що клієнт не зможе перелетіти з аеропорту A до B, користуючись лише літаками авіакомпанії OlympAirways. Для дослідження подібних ситуацій науковий відділ компанії ввів поняття числа вразливості зв’язку між парою аеропортів A та B. Це число дорівнює кількості рейсів авіакомпанії, відміна довільного з яких (при умові, що всі інші рейси виконуються у звичайному порядку) призведе до неможливості перельоту до аеропорту B з аеропорту A.
Завдання
Напишіть програму WEATHER, яка за інформацією про усі рейси, що виконуються авіакомпанією, визначає суму чисел вразливості зв’язку між усіма парами аеропортів.
Вхідні дані
Перший рядок вхідного файлу WEATHER.DAT містить ціле число N (1≤N≤100) – кількість аеропортів, що обслуговуються авіакомпанією. Другий рядок містить ціле число M (1≤M≤4950) – кількість рейсів, які виконуються авіакомпанією. Кожний з наступних M рядків визначає рейс, який представлено парою цілих чисел від 1 до N — номерами аеропортів, які він сполучає.
Вихідні дані
Єдиний рядок вихідного файлу WEATHER.SOL має містити ціле число – сумарне число вразливості зв’язку між усіма різними парами аеропортів A та B, таких, що номер A менше за номер B.
Приклад вхідних та вихідних даних
|
WEATHER.DAT |
WEATHER.SOL |
|
5 5 1 2 4 2 4 5 3 2 3 1 |
10 |
Шоколадні плитки (100 балів)
Напевно, всім відомо, що шоколад корисний для мозку людини. Тому учасники національної олімпіади країни Олімпія принесли на тур багато плиток шоколаду, щоб ґеніальні ідеї приходили до них швидше. Але принесеного шоколаду виявилося забагато, і після туру в кабінеті залишилося N прямокутних плиток, які складалися з часток розмірами 1×1. Двоє учасників вирішили з’їсти частину шоколаду, що залишився, але, враховуючи те що протягом туру вони скоштували досить багато шоколаду, було вирішено зробити це у досить незвичайний ігровий спосіб, за наступними правилами.
Учасники виконують певні операції з шоколадними плитками по черзі: спочатку перший, потім другий, знову перший і т.д. У свою чергу учасник обирає плитку шоколаду, з якою він буде виконувати одну з наступних операцій:
1) Розламати плитку на дві; лінія розлому повинна проходити паралельно сторонам плитки та між частками.
2) Відламати та з’їсти довільний «рядок» або «стовпчик» плитки, який не є крайнім.
3) Відламати та з’їсти всі частки плитки, що знаходяться з краю, але щоб після цього від плитки залишилася принаймні одна частка (мінімальний розмір плитки, з якою може бути виконана така операція – 3×3).
Жодна з цих операцій не може бути виконана з плиткою 1×1, тому всі такі плитки залишаються до кінця гри. Програє той учасник, який у свою чергу не зможе зробити жодної з наведених операцій.
Завдання
Напишіть програму CHOCO, яка за інформацією про плитки шоколаду, що залишилися після туру, визначає кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні виграшної стратегії в подальшому.
Вхідні дані
У першому рядку вхідного файлу CHOCO.DAT міститься ціле число N (1≤N≤100) – кількість шоколадних плиток. У другому рядку містяться N пар цілих чисел, кожна i-та з яких задає довжину та ширину i-ої плитки. Довжина та ширина не менші за 1 та не перевищують 100.
Вихідні дані
У єдиному рядку вихідного файлу CHOCO.SOL повинно міститися ціле число – кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні оптимальної стратегії в подальшому.
Приклад вхідних та вихідних даних
|
CHOCO.DAT |
CHOCO.SOL |
|
1 3 3 |
3 |
Виграшні ходи першого учасника наступні: операція (3), операція (2) з другим рядком, та операція (2) з другим стовпчиком
Другий тур
Працівники (100 балів)
На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.Існують правила, за якими визначається чи можна обробляти деталь на певному верстаті.
1) Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.
2) У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.
Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.
Завдання
Напишіть програму STAFF, що за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.
Вхідні дані.Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2≤N≤28) – кількість деталей яку необхідно обробити.
Вихідні дані.Єдиний рядок вихідного файлу STAFF.SOL має містити ціле число – максимальну можливу кількість працівників заводу.
Приклад вхідних та вихідних даних
|
STAFF.DAT |
STAFF.SOL |
|
4 |
2 |
Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станке B – детали 2 та 4. Інших варіантів послідовності обробки немає.
Робот (100 балів)
Робот рухається по полю, яке складається з N клітинок, що вишикувані у ряд. На кожній з клітинок знаходиться кубик певного кольору. На початку руху робот знаходиться на першій клітині поля та не тримає жодного кубика. Знаходячись на клітині, робот може виконати не більше одного разу кожну з наступних операцій: (1) покласти кубик того ж кольору, що лежить на поточній клітині; (2) підняти з клітини той кубик, що знаходився там спочатку. Після цього робот переміщується на наступну клітину або зупиняється, якщо поточна клітина є останньою у полі. Одночасно робот може тримати не більше ніж K кубиків. На момент зупинки робот не повинен тримати жодного кубика.
Завдання
Напишіть програму ROBOT, що за інформацією про колір кубиків та обмеження на кількість кубиків, яку може тримати робот, визначає максимальну загальну кількість кубиків, яку робот може перенести з місця на місце, рухаючись полем.
Вхідні дані
Перший рядок вхідного файлу ROBOT.DAT містить літерний рядок довжини N (1≤N≤1000). Рядок складається з маленьких літер латинського алфавіту. Кожна літера відповідає клітині поля та визначає колір кубика, що знаходиться у цій клітині. Другий рядок містить обмеження на кількість кубиків, яку одночасно може тримати робот K (1≤K≤25).
Вихідні дані. Єдиний рядок вихідного файлу ROBOT.SOL має містити ціле число — максимальну кількість кубиків, місцезнаходження яких робот може змінити рухаючись полем.
Приклад вхідних та вихідних даних
|
ROBOT.DAT |
ROBOT.SOL |
|
rgbbggrmcm 2 |
4 |
Зала Круглих Столів (100 балів)
Єдиний спосіб потрапити до Зали Круглих Столів – пройти через Колонний Коридор. Стіни Коридору зображаються на карті прямими лініями, які паралельні вісі OY системи координат. Вхід в коридор знаходиться знизу, а вихід з Коридору до Зали – зверху. В Коридорі є циліндричні (на карті круглі) Колони однакового радіуса R.
Завдання.Напишіть програму TABLE, що за інформацією про розміри Коридору, та розміщення Колон визначає діаметр найбільшого з Круглих Столів, який можна пронести через такий Коридор, зберігаючи поверхню Стола горизонтальною.
Вхідні дані.У першому рядку вхідного файлу TABLE.DAT задані два числа XL та XR – x-координати лівої та правої стін Коридору. У другому рядку знаходиться ціле число R (1≤R≤1 000 000) – радіус усіх Колон. У третьому – ціле число N (1≤N≤200), що задає кількість Колон. Далі йдуть N рядків, в кожному з яких по два числа – x- та y-координати центра відповідної Колони.Всі вхідні координати – цілі числа, що за модулем не перевищують 1 000 000.
Вихідні дані
Єдиний рядок вихідного файлу TABLE.SOL має містити єдине число – шуканий діаметр найбільшого Столу. Діаметр потрібно виводити з точністю 3 знаки після десяткової крапки (навіть у випадку, якщо він виявиться цілим). Якщо не можна пронести жодного Столу, то відповідь має бути: 0.000
Точність 3 знаки після крапки, за звичайними правилами заокруглення, означає, що відповідь, яка видається у вихідний файл, повинна відрізнятися від точної не більше ніж на 5×10-4 (тобто на 0.0005). Наприклад, якщо точна відповідь 1.234567, то у файлі повинно знаходитися число 1.235. Якщо точна відповідь 5.0005, то необхідно заокруглювати у більшу сторону, тобто у файл необхідно видати 5.001
Приклад вхідних та вихідних даних
|
TABLE.DAT |
TABLE.SOL |
|
0 90 3 4 10 10 70 10 50 50 10 90 |
47.000 |