IV Всероссийская олимпиада школьников по информатике
Троицк, 22-27 марта 1992 года
Задачи
Задача 1. Ломаные
Пусть W - множество всех замкнутых односвязных ломанных
на координатной плоскости xOy, удовлетворяющих условиям:
- каждые два соседних звена ломанной взаимно перпендикулярны;
- каждое звено ломанной параллельно одной из осей координат;
- отсутствуют самопересечения или самокасания ломанной;
- (x1, y1), ...,
(хN, yN) - целочисленные
координаты всех точек,
где ломанная претерпевает излом (порядок нумерации произволен и неизвестен),
N - количество изломов.
Требуется
- Написать по взможности оптимальные (по времени исполнения)
программы с обоснованием алгоритмов), которые по задаваемым
N и (x1, y1), ...,
(хN, yN) выдавали
бы и отображали на экране монитора:
- какую-либо ломанную из множества W;
- ломанную из множества W, имеющую
наибольшую длину, и значение этой длины;
- ломанную из множества W, ограничивающую
наибольшую площадь, и значение этой площади;
- количество ломанных в множестве W.
-
Решить задачу А, исключив пункт b) из определения W.
Примечание
Односвязной называется ломанная, из любой точки которой можно
попасть в любую другую ее точку, двигаясь по этой ломанной.
Задача 2. Компостеры
В билете пассажира оказалось пробито отверстий больше, чем
штырей в компостере. Пассажир утверждал, что пользовался только
одним компостером, но случайно нажал его несколько раз.
Контролеру требуется определить, могло ли быть получено заданное
расположение отверстий одним и тем же компостером, если билет можно
пробивать с обеих сторон неограниченное число раз и произвольно перемещать
и поворачивать относительно компостера. Пробитые отверстия не
выходят за пределы билета. В билете было пробито N (N < 10)
отверстий.
Требуется:
- Для компостера с двумя штырями (S=2) составить программу, которая:
- Определяет, можно ли получить заданным компостером требуемое
расположение отверстий в билете. Если это возможно, то
изображает вид билета после каждого нажатия компостера.
В противном случае, выводит соответствующие сообщение.
- Определяет количество K различных компостеров,
каждым из которых можно пробить заданную конфигурацию.
- При K=0 (см. пункт 2) находит компостер,
с помощью которого можно пробить наибольшее количество из заданных отверстий.
- Находит минимальное число нажатий, требуемое для пробивки
заданной конфигурации отверстий, для каждого компостера из пункта 2.
- Решить задачу А для компостеров с числом штырей S (S > 2).
Примечания
Все исходные данные - натуральные числа. Компостеры,
дающие при однократном нажатии совпадающие конфигурации отверстий,
считаются одинаковыми. Относительное расположение отверстий в билете
и штырей в компостере вводятся либо с клавиатуры, либо из файла
с именем COMP.DAT. Структура вводимой информации:
{N,
x1, y1, ...,
xN, yN,
S,
u1, v1, ...,
uS, vS},
где
xi, yi
- коодинаты отверстий в билете,
ui, vi
- координаты штырей в компостере. Нажатие компостера
следует моделировать клавишей "Пробел". При выводе конфигурации
на экран следует изображать координатную сетку. При
этом программа должна осуществлять подходящее
масштабирование.