|
XVI Всеукраїнська олімпіада з інформатики ВТО (100 балів) Територія Великої Трикутної Області (ВТО) являє собою прямокутний трикутник. Довжини його катетів дорівнюють M та N державних одиниць довжини (ДОД). Уряд ВТО вирішив покрити якомога більшу частину території області квадратними плитами розміром 1x1 ДОД. Плити мають щільно прилягати одна до одної та до катетів ВТО. Різати плити не можна. Завдання Напишіть програму TRIANGLE, яка за довжинами катетів ВТО та місткістю контейнера знаходить кількість плит, що залишаться на складі після виконання проекту.
Вихiднi данi Єдиний рядок вихідного файлу TRIANGLE.SOL має містити ціле число - кількість невикористаних плит з останнього контейнера. Приклад вхiдних та вихiдних даних
Вишня (100 балів) Маленьке, але горде мишеня вирішило з'їсти усі ягоди з дерева вишні. Вишня - це звичайне дерево, гілки якого розгалужуються і надалі не зростаються. З точки, де закінчується гілка, можуть починатися інші гілки або може рости деяка кількість ягід. Завдання Напишіть програму CHERRY, що за інформацією про дерево визначає мінімальну кількість одиниць КР яку мишеня повинно мати, щоб з'їсти усі ягоди з дерева та повернутися на землю. При цьому, на протязі руху мишеня поточний запас КР не може бути від'ємним.
Приклад вх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) - кількість наявних спочатку речовин, а також номер цільової речовини. Вихiднi данi Єдиний рядок вихідного файлу ALCHEMY.SOL повинен містити ціле число - знайдений мінімальний час, за який може бути отримана цільова речовина. Приклад вхiдних та вихiдних даних
XVI Всеукраїнська олiмпiада з iнформатики Є 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в)
Завдання Напишіть програму 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 рядків, кожен з яких задає координату клітини поля на поточному кроці. Координата являє собою пару натуральних чисел: номер рядка та номер стовпчика клітини поля. Приклад вхiдних та вихiдних даних
Система рiвнянь (100 балiв) Нехай k-те рівняння системи з N рівнянь має вигляд X+Y=bk, де X=x1k+x2k+...+xk-1 k; Y=xk k+1+...+xk N. Таким чином, ліва частина кожного рівняння має N-1 доданок та кожне невідоме зустрічається рівно в двох рівняннях системи. Завдання Напишіть програму SYSTEM, що за заданими b1,...,bN знаходить один з розв'язків системи, при умові що невідомі xij можуть набувати лише значення 0 або 1. Вхiднi данi В першому рядку вхідного файлу SYSTEM.DAT знаходиться натуральне число - кількість тестових блоків. Кожний тестовий блок починається з рядка, який містить число N (3<=N<=50) - кількість рівнянь у системі. У другому рядку блока знаходиться N цілих чисел bi (0<=bi<=50). Вихiднi данi
Приклад вхiдних та вихiдних даних
|
