ХVІ Всеукраинская олимпиада
(г. Донецк, март 2003г.)
Первый тур
ВТО (100 баллов)
Територия Виликой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть територии области квадратными плитами размером 1x1 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.
Согласно межгосударственным соглашениям, правительство ВТО не имеет права покрыть частью своей плиты чужую територию. Производитель поставляет плиты только контейнерными партиями — по P плит. Правительство заказывает столько контейнеров, сколько необходимо для реализации проекта.
Заведующий центральным складом, узнав про проект, решил, что его интересует количество плит, которые останутся на складе из последнего контейнера после покрытия територии ВТО.
Задание
Напишите программу TRIANGLE, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.
| Входные данные Единственная строка входного файла TRIANGLE.DAT содержит три целых числа: M, N (2<=M, N<=2 000 000 000) и P (100<=P<=10 000). Выходные данные Единственная строка выходного файла TRIANGLE.SOL должна содержать целое число — количество неиспользованных плит из последнего контейнера. |
 |
Пример входных и выходных данных
| TRIANGLE.DAT |
TRIANGLE.SOL |
| 4 3 100 | 97 |
Вишня (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 должно находится целое число — минимальное количество единиц ПВ, которое должен иметь мышонок, для восхождения на дерево, съедания всех ягод и возвращения на землю. |
 |
Пример входных и выходных данных
| CHERRY.DAT |
CHERRY.SOL |
| 8 5 3 6 5 7 5 0 10 9 0 1 4 0 19 11 0 50 5 2 2 4 3 2 8 3 4 0 0 |
15 |
Алхимия (100 баллов)
Известны K видов веществ и N типов алхимических реакций. Каждая реакция по набору входных веществ продуцирует набор выходных. Проведение каждой реакции требует фиксированного времени. Любые вещества, полученные в результате реакций, можно выделять в чистом виде для отдельного использования. Каждого вещества всегда достаточно для любого использования. Вещество, полученное в результате только что закончившейся реакции, можно сразу же использовать в других реакциях. Реакции могут проходить одновременно.
Задание
Напишите программу ALCHEMY, которая по информации об известных веществах и реакциях определяет за какое наименьшее время можно получить целевое вещество.
Входные данные
Первая строка входного файла ALCHEMY.DAT содержит четыре целых числа: K (3<=K<=250) — количество веществ, N (3<=N<=500) — количество реакций, M (1<=M<K) — количество имеющихся сначала веществ, а также номер целевого вещества.
Далее следуют N блоков, которые описывают реакции. Каждый блок состоит из трех строк: первая содержит натуральное число — время, необходимое для проведения реакции, вторая строка — количество веществ, которые вступают в реакцию, и перечень этих веществ, третья строка — количество веществ, которые образовываются в результате реакции, и их перечень.
Вещества, имеющиеся сначала, имеют номера от 1 до M, а все остальные — от M+1 до K. Сумма времен проведения всех реакций не превышает 2*109.
Выходные данные
Единственная строка выходного файла ALCHEMY.SOL должна содержать целое число — найденное минимальное время, за которое может быть получено целевое вещество.
Если получить целевое вещество невозможно, единственная строка выходного файла должна содержать число -1.
Для приведенного примера входных данных, целевое вещество 4 можно получить, если на протяжении первых трех единиц времени провести реакцию 2, а после этого на протяжении двух единиц времени провести реакцию 3. Таким образом, за 5 единиц времени будет получено требуемое вещество.
Пример входных и выходных данных
| ALCHEMY.DAT | ALCHEMY.SOL |
| 4 3 1 4 8 1 1 1 4 3 1 1 2 2 3 2 2 1 3 1 4 |
5 |
Второй тур
Цепь (100 баллов)
Есть N кусков цепи, каждый i-й из которых содержит Li звеньев. Можно разгибать произвольные звенья и потом сгибать их снова, соединяя отдельные куски.
Задание
Напишите программу CHAIN, которая по количеству кусков цепи N и количеству звеньев в кусках Li определяет минимальное количество звеньев, которые нужно разогнуть и согнуть снова, чтобы соединить все куски в одну цепь. Цепь не может иметь разветвлений, т.е. каждое звено должно быть соединено с двумя звеньями (кроме двух звеньев по краям цепи, которые должны быть соединены только с одним звеном).
Входные данные
В первой строке входного файла CHAIN.DAT находится целое число N (2<=N<=10 000). Во второй строке находятся N целых чисел Li (1<=Li<=1 000 000 000).
Выходные данные
В единственной строке выходного файла CHAIN.SOL должно находится целое число — наименьшее количество звеньев, которые необходимо разогнуть и согнуть снова, чтобы получить одну цепь из всех кусков.
Пример входных и выходных данных
| CHAIN.DAT | CHAIN.SOL |
| 3 100 3 4 |
2 |
Казино (100 баллов)
| В верхнем левом углу прямоугольного поля размерами N<=M размещается игральний кубик, разворот которого изображен на рисунке. Кубик ориентирован так, что передней грани соответствует единица, а слева находится грань, которой соответствует двойка. Клетки поля квадратные, их размеры совпадают с размерами грани кубика. Кубик может двигаться по полю, переворачиваясь через одно из ребер, и попадать при этом в соседнюю снизу, сверху, справа или слева клетку поля. Например, если из начального состояния кубик двигается направо, то передней станет грань с двойкой, а если вниз — то с тройкой. Кубик не может выходить за пределы поля. |
 |
Задание
Напишите програму CASINO, которая по информации о поле находит один из возможных путей кубика из верхнего левого угла в нижний правый угол поля. При этом необходимо найти такой путь, чтобы верхняя грань кубика в целевой клетке имела максимальное возможное значение. Кубик может посещать каждую клетку поля несколько раз.
Входные данные
| Первая строка входного файла CASINO.DAT содержит два натуральных числа N и M (2<=N, M<=50), которые определяют высоту и ширину поля соответственно. Далее задается поле, которое представлено N строками, каждая из которых состоит из M чисел, каждое из которых равно 0 либо 1. В случае, когда клетке поля соответствует число 1, кубику запрещено посещать данную клетку. В противном случае эта клетка может встречаться в пути кубика. Начальной клетке всегда соответствует число 0. |  |
Выходные данные
Первая строка выходного файла CASINO.SOL должна содержать натуральное число W — длину найденого пути. Далее в файле должны находиться W строк, каждая из которых задает координату клетки поля на текущем шаге. Координата представляет собой пару натуральных чисел: номер строки и номер столбца клетки поля.
В случае, когда искомого пути не существует, выходной файл должен содержать строку с числом -1.
Пример входных и выходных данных
| CASINO.DAT | CASINO.SOL |
| 3 2 0 1 0 0 0 0 |
3 2 1 2 2 3 2 |
Система уравнений (100 баллов)
Пусть k-ое уравнение системы из N уравнений имеет вид X+Y=bk, где X=x1k+x2k+…+xk-1 k; Y=xk k+1+…+xkN. Таким образом, левая часть каждого уравнения имеет (N-1)-но слагаемое и каждое неизвестное встречается ровно в двух уравнениях системы.
Задание
Напишите программу SYSTEM, которая по заданным b1,…,bN находит одно из решений системы, при условии что неизвестные xij могут принимать только значения 0 либо 1.
Входные данные
В первой строке входного файла SYSTEM.DAT находится натуральное число — количество тестовых блоков. Каждый тестовий блок начинается со строки, которая содержит число N (3<=N<=50) — количество уравнений в системе. Во второй строке блока находится N целых чисел bi (0<=bi<=50).
Выходные данные
Для каждого тестового блока в выходной файл SYSTEM.SOL должно быть записано одно из решений системи: (N-1)-на строка, каждая k-ая из которых содержит N-k чисел — найденных значений неизвестных:
x12 … x1N
x23 … x2N
x34 … x3N
…
xN-1 N
Если система не имеет решений для тестового блока, в выходной файл должна быть записана строка, которая содержит единственное число -1.
|
Пример входных и выходных данных
|
 |
| Полный архив олимпиады (1.2 Мб) |