Предисловие оргкомитета и жюри
Уважаемые участники олимпиады!
Предлагаем вашему вниманию задачи 4-го,последнего тура. Максимальное число баллов, которые можно набрать в этом туре- 400. Письма с решениями, оформленные по правилам(!), отправляйте по адресу olymp@olymp.vinnica.ua в любое удобное для вас время с 12 по 20 марта 2001 г.
Задача Composetr4a
Сравнение компостеров
Компостер в автобусе делает в билете отверстия, что содержатся в некоторых узлах квадратной сетки размером M*N узлов. Компостеры считаются одинаковыми, если все сделанные ими отверстия в билетах можно совместить, отобразив один билет на другой комбинацией параллельных переносов, поворотов на прямой угол и симметрий относительно горизонтальной и вертикальной осей. Закомпостированный билет имеет по крайней мере одно отверстие.
ЗАДАНИЕ: Написать программу, определяющую, одинаковы ли два заданных компостера.
Ограничения: 2<=M<=15 2<=N<=15
Ввод-вывод
Ваша программа должна прочитать с клавиатуры два числа M и N через пробел,а далее, в M строках по N едениц или нолей через пробел, а потом - то же самое для второго компостера. Вывести на экран результат в виде слов "Alike", если компостеры одинаковы или "Different", если разные.
Пример 1.
Ввод >3
Ввод >3
Ввод> 0 0 0
Ввод> 0 0 1
Ввод> 0 0 0
Ввод >3
Ввод >4
Ввод > 0 1 0 0
Ввод > 0 0 0 0
Ввод > 0 0 0 0
Вывод> Alike
{хоть он второй компостер и имеет не такой размер, как первый} {но считается одинаковым с ним}
Пример 2.
Ввод >4
Ввод >6
Ввод >1 0 0 0 0 0
Ввод >0 0 0 0 0 0
Ввод >0 0 0 0 0 0
Ввод >0 0 0 0 1 0
Ввод >4
Ввод >6
Ввод >1 0 0 0 0 1
Ввод >0 0 0 0 0 0
Ввод >0 0 0 0 0 0
Ввод >0 0 0 0 0 0
Вывод>Different
Задача Composetr4b
Количество компостеров
Используя условие предыдущей задачи, определите количество различных компостеров, которые можно образовать на сетке размером M*N узлов.
Ограничения: 2<=M<=15 2<=N<=15
Ввод-вывод
Ваша программа должна прочитать с клавиатуры два числа M и N через пробел и вывести на экран число различных компостеров
Пример
Ввод> 2 2
Вывод > 5
Задача Tool4
Изделие состоит из N деталей. Имеется N станков, на каждом из которых можно
изготовить любую деталь. Для каждых станка и деталей известно время t[i,k] изготовления k-й детали на i-м станке. Напишите программу, определяющую, на
каком станке следует изготовить каждую деталь, чтобы одновременно начав изготовлять все детали, завершить изготовления всех деталей как можно раньше.
Ограничения: 1<=N<=50
Каждое из чисел t[i,1], t[i,2],...,t[i,N] натуральное и не превосходит 100.
Ввод-вывод: Ваша программа должна прочитать с клавиатуры число N, а затем в каждой из N строк содержит длительности изготовления деталей на соответствующем
станке t[i,1], t[i,2],...,t[i,N] через пробел.
На экран нужно вывести в одну строку номера деталей, которые надо
изготовить соответственно на 1-м, 2-м,..., N-м станках, разделив их пробелами. В следующую строку необходимо вывести время от начала до завершения изготовления всех деталей.
Пример
Ввод> 2
Ввод>3 2
Ввод>1 2
Вывод>2 1
Вывод>2
Задача RECT4
Прямоугольники
На плоскости задан многоугольник. Необходимо написать программу определяющую прямоугольник минимальной площади, который содержит в себе заданный многоугольник, который имеет N вершин.
Ограничения: Все координаты даются в виде действительных чисел в формате,который обрабатывается стандартными функциями ввода-вывода. Оптимальную площадь и координаты прямоугольника необходимо вычислить с точностью до 10-5. 3<=N<=3000,
Ввод-вывод: С клавиатуры вводится количество вершин N, а потом , в следующих N строках -по два действительных числа X Y (через пробел) - координаты вершин многоугольника в порядке их обхода по часовой стрелке. Программа должна вывести на экран 5 строк: в первой строке число S - площадь прямоугольника, а в следующих 4-х строках - пары координат X Yi вершин прямоугольника в порядке их обхода (в произвольном направлении)
Пример:
Ввод>6
Ввод>0.0 0.0
Ввод>3.0 2.0
Ввод>4.0 4.0
Ввод>5.0 2.0
Ввод>8.0 0.0
Ввод>4.0 1.0
Вывод>32.0
Вывод>4.0 4.0
Вывод>0.0 8.0
Вывод>4.0 -4.0
Вывод>0.0 0.0
Задача CARDS4
Головоломка.
На планете Олимпия очень популярна такая головоломка. На столе последовательно лежат N стопок разноцветных карточек.За один ход можно снять верхние карточки одного цвета с произвольного количества размещенных рядом стопок.
Задание Написать программу CARDS, которая будет вычислять минимальное оличество ходов, необходимое для того, чтобы снять все карточки на столе.
Ограничения:
N>=2
K>= 1
(1<= N*K<=10000)
Ввод-вывод: Вводим с клавиатуры в первой строке число стопок N.Каждая i-я строка из последующих N строк содержит через пробел количество карточек в i-й стопке и последовательность из K натуральных чисел, которые определяют цвета карточек в i-й стопке, начиная с самой нижней.Вывод производится на экран.
Пример.
Ввод>2
Ввод>2 1 2
Ввод>3 3 1 2
Вывод>3