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

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

Задачи

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

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

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

Требуется

  1. Написать по взможности оптимальные (по времени исполнения) программы с обоснованием алгоритмов), которые по задаваемым N и (x1, y1), ..., (хN, yN) выдавали бы и отображали на экране монитора:
    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, x1, y1, ..., xN, yN, S, u1, v1, ..., uS, vS}, где xi, yi - коодинаты отверстий в билете, ui, vi - координаты штырей в компостере. Нажатие компостера следует моделировать клавишей "Пробел". При выводе конфигурации на экран следует изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование.