Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Завдання 4-го туру олімпіади.

Предисловие оргкомитета и жюри

Уважаемые участники олимпиады!

Предлагаем вашему вниманию задачи 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

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"