XVI Всеукраїнська олімпіада з інформатики
Перший тур

ВТО (100 балів)

Територія Великої Трикутної Області (ВТО) являє собою прямокутний трикутник. Довжини його катетів дорівнюють M та N державних одиниць довжини (ДОД). Уряд ВТО вирішив покрити якомога більшу частину території області квадратними плитами розміром 1x1 ДОД. Плити мають щільно прилягати одна до одної та до катетів ВТО. Різати плити не можна.
        Згідно міждержавних угод, уряд ВТО не має права покрити частиною своєї плити чужу територію. Виробник поставляє плити лише контейнерними партіями - по P плит. Уряд замовляє стільки контейнерів, скільки необхідно для реалізації проекту.
        Завідуючий центральним складом, дізнавшись про цей проект, вирішив, що його цікавить кількість плит, які залишаться на складі з останнього контейнера після покриття території ВТО.

Завдання

Напишіть програму TRIANGLE, яка за довжинами катетів ВТО та місткістю контейнера знаходить кількість плит, що залишаться на складі після виконання проекту.

Вхiднi данi Єдиний рядок вхідного файлу TRIANGLE.DAT містить три цілих числа: M, N (2<=M, N<=2 000 000 000) та P (100<=P<=10 000).

Вихiднi данi

Єдиний рядок вихідного файлу TRIANGLE.SOL має містити ціле число - кількість невикористаних плит з останнього контейнера.

Приклад вхiдних та вихiдних даних

Вишня (100 балів)

Маленьке, але горде мишеня вирішило з'їсти усі ягоди з дерева вишні. Вишня - це звичайне дерево, гілки якого розгалужуються і надалі не зростаються. З точки, де закінчується гілка, можуть починатися інші гілки або може рости деяка кількість ягід.
        Гілки дерева настільки довгі, що мишеня помітно виснажується, коли повзе по них. Коли мишеня проповзає по гілці один метр, воно втрачає одиницю запасу корисних речовин (КР), що містяться в його організмі. З'їдання однієї вишні поповнює запас КР на одиницю. Якщо запас КР стає від'ємним, мишеня гине.

Завдання

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

Вхiднi данi У першому рядку вхідного файлу CHERRY.DAT міститься ціле число N (1<=N<=100) - кількість гілок у дереві. Далі йдуть N рядків, що описують дерево. Кожен (i+1)-ий рядок файлу задає інформацію про i-ту гілку. Першим у рядку йде ціле число L (1<=L<=30 000), що задає довжину гілки. Другим - кількість гілок K, що починаються з кінця i-ої гілки. Далі слідує K чисел - номери цих гілок. Якщо число K для гілки дорівнює нулю, то третє число задає кількість ягід V (0<=V<=30 000), що ростуть на кінці гілки. Вихiднi данi У єдиному рядку файлу CHERRY.SOL повинно знаходитися ціле число - мінімальна кількість одиниць КР, яку повинно мати мишеня, для сходження на дерево, з'їдання усіх ягід та повернення на землю.

Приклад вхiдних та вихiдних даних

Алхімія (100 балів)

Відомі K видів речовин та N типів алхiмiчних реакцій. Кожна реакція за набором вхідних речовин продукує набір вихідних. Проведення кожної реакції потребує фіксованого часу. Будь-які речовини, отримані внаслідок реакцій, можна виділяти в чистому вигляді для окремого використання. Кожної речовини завжди достатньо для будь-якого використання. Речовину, щойно утворену внаслідок реакції, можна відразу ж використовувати в інших реакціях. Реакції можуть проходити одночасно.

Завдання

Напишіть програму ALCHEMY, яка за інформацією про існуючі речовини та реакції визначає за який найменший час можна одержати цільову речовину.

Вхiднi данi

Перший рядок вхідного файлу ALCHEMY.DAT містить чотири цілих числа: K (3<=K<=250) - кількість речовин, N (3<=N<=500) - кількість реакцій, M (1<=M < K) - кількість наявних спочатку речовин, а також номер цільової речовини.
        Далі йдуть N блоків, що описують реакції. Кожен блок складається з трьох рядків: перший містить натуральне число - час, необхідний для проведення реакції, другий рядок - кількість речовин, що вступають до реакції, та перелік цих речовин, третій рядок - кількість речовин, що утворюються внаслідок реакції, та їх перелік.
        Речовини, наявні спочатку, мають номери від 1 до M, а всі інші - від M+1 до K. Сума часів проведення всіх реакцій не перевищує 2•10⁹.

Вихiднi данi

Єдиний рядок вихідного файлу ALCHEMY.SOL повинен містити ціле число - знайдений мінімальний час, за який може бути отримана цільова речовина.
        Якщо отримати цільову речовину неможливо, єдиний рядок вихідного файлу має містити число -1.
        Для наведеного прикладу вхідних даних, цільову речовину 4 можна отримати, якщо на протязі перших трьох одиниць часу провести реакцію 2, а після цього на протязі двох одиниць часу провести реакцію 3. Таким чином, за 5 одиниць часу буде отримана потрібна речовина.

Приклад вхiдних та вихiдних даних

XVI Всеукраїнська олiмпiада з iнформатики
Другий тур

Ланцюг (100 балів)

Є N шматків ланцюга, кожен i-й з яких містить Li ланок. Можна розгинати довільні ланки та потім згинати їх знову, з'єднуючи окремі шматки.

Завдання

Напишіть програму CHAIN, що за кількістю шматків ланцюга N та кількістю ланок у шматках Li визначає мінімальну кількість ланок яку потрібно розігнути та зігнути знову, щоб з'єднати усі шматки в один ланцюг. Ланцюг не може мати розгалужень, тобто кожна його ланка повинна бути з'єднана з двома іншими ланками (крім двох ланок з країв ланцюга, що повинні бути з'єднані лише з однією ланкою).

Вхiднi данi

В першому рядку вхідного файлу CHAIN.DAT знаходиться ціле число N (2<=N<=10000). В другому рядку знаходяться N цілих чисел Li (1 <= Li <= 1 000 000 000).

Вихiднi данi

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

Приклад вхiдних та вихiдних даних

Казино (100 балiв)

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

Завдання

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

Вхiднi данi

Перший рядок вхідного файлу CASINO.DAT містить два натуральних числа N та M (2<=N, M<=50), що визначають висоту та ширину поля відповідно. Далі задається поле, яке представлене N рядками, кожен з яких складається з M чисел, кожне з яких дорівнює 0 або 1. У випадку, коли клітині поля відповідає число 1, кубику заборонено відвідувати дану клітину. В іншому разі ця клітина може зустрічатись у шляху кубика. Початковій клітині завжди відповідає число 0.

Вихiднi данi

Перший рядок вихідного файлу CASINO.SOL повинен містити натуральне число W - довжину знайденого шляху. Далі у файлі мають знаходитися W рядків, кожен з яких задає координату клітини поля на поточному кроці. Координата являє собою пару натуральних чисел: номер рядка та номер стовпчика клітини поля.
        У випадку коли шуканого шляху не існує, вихідний файл має містити рядок з числом -1.

Приклад вхiдних та вихiдних даних

Система рiвнянь (100 балiв)

Нехай k-те рівняння системи з N рівнянь має вигляд X+Y=b_k, де X=x_1k+x_2k+...+x_{k-1 k}; Y=x_{k k+1}+...+x_{k N}. Таким чином, ліва частина кожного рівняння має N-1 доданок та кожне невідоме зустрічається рівно в двох рівняннях системи.

Завдання

Напишіть програму SYSTEM, що за заданими b₁,...,b_N знаходить один з розв'язків системи, при умові що невідомі xij можуть набувати лише значення 0 або 1.

Вхiднi данi

В першому рядку вхідного файлу SYSTEM.DAT знаходиться натуральне число - кількість тестових блоків. Кожний тестовий блок починається з рядка, який містить число N (3<=N<=50) - кількість рівнянь у системі. У другому рядку блока знаходиться N цілих чисел b_i (0<=b_i<=50).

Вихiднi данi

Для кожного тестового блоку до вихідного файлу SYSTEM.SOL повинен бути записаний один з розв'язків системи: N-1 рядків, кожен k-й з яких містить N-k чисел - знайдених значень невідомих: x12 … x1N x23 … x2N x34 … x3N … xN-1 N Якщо система не має розв'язків для тестового блоку, у вихідний файл повинен бути записаний рядок, що містить єдине число -1.

Приклад вхiдних та вихiдних даних

SYSTEM.DAT SYSTEM.SOL 2 3 1 2 3 5 3 2 3 2 2 -1 1 1 1 0 0 0 1 1 1 0