Написання програм TRIANGLE, CHERRY і ALCHEMY (Завдання першого туру XVI Всеукраїнської олiмпiади з iнформатики)

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

Перший тур

ВТО (100 балів)

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

Згідно міждержавних угод, уряд ВТО не має права покрити частиною своєї плити чужу територію. Виробник поставляє плити лише контейнерними партіями — по P плит. Уряд замовляє стільки контейнерів, скільки необхідно для реалізації проекту.

Завідуючий центральним складом, дізнавшись про цей проект, вирішив, що його цікавить кількість плит, які залишаться на складі з останнього контейнера після покриття території ВТО.

Завдання

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

Вхідні дані

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

Вихідні дані

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

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

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

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

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

Завдання

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

Рух завжди починається та закінчується на початку гілки з номером 1, що відповідає стовбуру.

Вхідні дані

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

Вихідні дані

У єдиному рядку файлу CHERRY.SOL повинно знаходитися ціле число — мінімальна кількість одиниць КР, яку повинно мати мишеня, для сходження на дерево, з’їдання усіх ягід та повернення на землю.

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

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

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

Завдання

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

Вхідні дані

Перший рядок вхідного файлу ALCHEMY.DAT містить чотири цілих числа: K (3≤K≤250) — кількість речовин, N (3≤N≤500) — кількість реакцій, M (1≤M<K) — кількість наявних спочатку речовин, а також номер цільової речовини.

Далі йдуть N блоків, що описують реакції. Кожен блок складається з трьох рядків: перший містить натуральне число — час, необхідний для проведення реакції, другий рядок — кількість речовин, що вступають до реакції, та перелік цих речовин, третій рядок — кількість речовин, що утворюються внаслідок реакції, та їх перелік.

Речовини, наявні спочатку, мають номери від 1 до M, а всі інші — від M+1 до K. Сума часів проведення всіх реакцій не перевищує 2∙10⁹.

Вихідні дані

Єдиний рядок вихідного файлу ALCHEMY.SOL повинен містити ціле число — знайдений мінімальний час, за який може бути отримана цільова речовина.