Задача 27.
КОМПОСТЕР
Авторы: АНДРЕЕВА Е.В. МАРЧЕНКО А.П.
В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал на него несколько раз. Контролеру требуется определить, могло ли быть получено заданное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N<10) отверстий.
ТРЕБУЕТСЯ:
А. Для компостера с двумя штырями (S=2) составить программу, которая:
1. Определяет, можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изображает вид билета после каждого нажатия компостера. В противном случая, выводит соответствующее сообщение.
2. Определяет количество K различных компостеров каждым из которых можно пробить заданную конфигурацию.
3. При K=0 (см. п.2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий.
4. Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2.
Б. Решить задачу А для компостеров с числом штырей S (S>2).
ПРИМЕЧАНИЯ.
* Все исходные данные - натуральные числа.
* Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми.
* Относительное расположение отверстий в билете и штырей в компостере вводится либо с клавиатуры, либо из файла с именем COMP.DAT .
Сруктура вводимой информации: {N,x[1],y[1],...,x[N],y[N],S,u[1],v[1],...,u[S],v[S]},
где x[i], y[i] - координаты отверстий в билете, u[i], v[i] - координаты штырей в компостере.
* Нажатие компостера (см. п.1) моделировать клавишей "Пробел".
* При выводе конфигурации на экран (см. п.п.1,3) изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование.
|
