IV Всероссийская олимпиада школьников по информатике

Троицк, 22-27 марта 1992 года

Задачи

Задача 1. Ломаные

Пусть W - множество всех замкнутых односвязных ломанных на координатной плоскости xOy, удовлетворяющих условиям:

1. каждые два соседних звена ломанной взаимно перпендикулярны;
2. каждое звено ломанной параллельно одной из осей координат;
3. отсутствуют самопересечения или самокасания ломанной;
4. (x₁, y₁), ..., (х_N, y_N) - целочисленные координаты всех точек, где ломанная претерпевает излом (порядок нумерации произволен и неизвестен), N - количество изломов.

Требуется

1. Написать по взможности оптимальные (по времени исполнения) программы с обоснованием алгоритмов), которые по задаваемым N и (x₁, y₁), ..., (х_N, y_N) выдавали бы и отображали на экране монитора:
   1. какую-либо ломанную из множества W;
   2. ломанную из множества W, имеющую наибольшую длину, и значение этой длины;
   3. ломанную из множества W, ограничивающую наибольшую площадь, и значение этой площади;
   4. количество ломанных в множестве W.
2. Решить задачу А, исключив пункт b) из определения W.

Примечание

Односвязной называется ломанная, из любой точки которой можно попасть в любую другую ее точку, двигаясь по этой ломанной.

Задача 2. Компостеры

В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал его несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N < 10) отверстий.

Требуется:

1. Для компостера с двумя штырями (S=2) составить программу, которая:
   1. Определяет, можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изображает вид билета после каждого нажатия компостера. В противном случае, выводит соответствующие сообщение.
   2. Определяет количество K различных компостеров, каждым из которых можно пробить заданную конфигурацию.
   3. При K=0 (см. пункт 2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий.
   4. Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2.
2. Решить задачу А для компостеров с числом штырей S (S > 2).

Примечания

Все исходные данные - натуральные числа. Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми. Относительное расположение отверстий в билете и штырей в компостере вводятся либо с клавиатуры, либо из файла с именем COMP.DAT. Структура вводимой информации: {N, x₁, y₁, ..., x_N, y_N, S, u₁, v₁, ..., u_S, v_S}, где x_i, y_i - коодинаты отверстий в билете, u_i, v_i - координаты штырей в компостере. Нажатие компостера следует моделировать клавишей "Пробел". При выводе конфигурации на экран следует изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование.