XVII Всеукраинская олимпиада по информатике 2004 г. г.Харьков
1 тур
Векторы (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), но не наоборот.
Последовательность из двух и более точек плоскости a 1, a 2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai +1 (1≤ i ≤ k -1 ), и ak соединена вектором с a 1. Циклы считаются разными если они отличаются хотя бы одной вершиной.
Задание
Напишите программу 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) Отломить и съесть все доли плитки, которые находятся с краю, но чтобы после этого от плитки осталась хотя бы одна доля (минимальный размер плитки, c которой может быть произведена такая операция – 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 |