Игра «О’Макс!»

Задача A. Игра «О’Макс!»

Ограничение по времени:	3 секунды (без учета времени работы модуля)
Ограничение по памяти:	32 мегабайта (без учета памяти, занимаемой модулем)
Максимальный балл:	100 баллов

Рассмотрим следующую игру. Дано N различных точек, расположенных на окружности и занумерованных в порядке обхода по часовой стрелке (2≤N≤50). Два игрока по очереди выполняют ходы. Ход заключается в том, что разрешается соединить какие-то две из этих точек отрезком так, чтобы он не пересекал уже проведенные отрезки и так, чтобы ни из какой вершины не выходило более одного отрезка. Проигрывает тот, кто не может сделать ход.

Напишите программу, которая, играя с модулем, реализует стратегию первого игрока.

Ваша программа должна использовать модуль game, у которого она будет получать входные данные, сообщать ему о собственных ходах, а также узнавать о ходах противника.

При инициализации игры вы должны вызвать функцию Init, которая вернет вам значение N. Для того, чтобы сообщить о своем ходе, вы должны вызвать процедуру Move и в качестве первых двух параметров передать ей два натуральных числа — номера вершин, которые вы соединяете отрезком на текущем ходе. В качестве третьего и четвертого параметров следует передать переменные, в которые модуль поместит номера вершин, которые он соединил хордой в качестве ответного хода. В случае, если модуль не может сделать ход, или после его хода сделать ход не сможете вы, то модуль автоматически завершит работу программы. Ваша программа не должна завершаться самостоятельно.

Free Pascal

function Init:integer;

procedure Move(u1,v1:integer; var u2,v2:integer);

GNU C/C++

int Init();

void Move(int u1, int v1, int* u2, int* v2);

Для тестирования собственных решений, вы можете использовать модуль game, который вы можете найти в каталоге game на диске Q. Данный модуль реализует некоторую (не обязательно наилучшую) стратегию второго игрока. Значение числа N он считывает из файла game. in. Результат игры он записывает на экран.

При тестировании вашего решения модуль game (в частности, имена входного и выходного файла, а также реализуемая модулем стратегия) может быть заменен.

Задача B. Склейка

Имя входного файла:	merge. in
Имя выходного файла:	merge. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

Дан ориентированный граф, вершины в котором занумерованы числами от 1 до N. В нем разрешается выполнять операцию склейки двух вершин, которая заключается в том, что из графа удаляются две вершины и добавляется одна новая вершина, в которую идут дуги из тех вершин, из которых были дуги хотя бы в одну из удаленных вершин, и из которой идут дуги во все вершины, куда шли дуги хотя бы из одной из удаленных вершин. Новая вершина получает в качестве своего номера минимальный из номеров склеиваемых вершин.

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

Формат входных данных

Первая строка входного файла содержит целые числа N и M — количество вершин и дуг в исходном графе (1 ≤ N ≤ 200). Следующие M строк содержат описания дуг, каждая из которых задается номером начальной и конечной вершины. Граф не содержит петель и кратных ребер.

Формат выходных данных

В выходной файл выведите K — число операций склейки. Далее выведите K пар чисел, задающих номера склеиваемых вершин.

Примеры

merge. in	merge. out
4 4 1 2 4 3 1 3 4 2	2 1 2 4 3

Задача C. Гора

Имя входного файла:	mountain. in
Имя выходного файла:	mountain. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

Недавно археологи Слегкаярославца нашли древнюю рукопись. В ней автор описывает свои похождения по горе Х загадочного материка Атлантида.

Известно, что гора имеет высоту H метров и длину L метров. Если расположить чертеж профиля горы на координатной плоскости так, что гора будет расположена в первой координатной четверти, ее самая левая точка будет иметь координаты (0, 0), а правая – (L, 0), то профиль горы будет иметь вид ломаной такого вида, что:

·  все вершины ломанной имеют целочисленные абсциссы и ординаты;

·  каждое звено ломаной либо параллельно оси абсцисс, либо наклонено к ней под углом 45 градусов;

·  существует хотя бы одна вершина ломаной с ординатой равной H и не существует вершин с ординатой больше H;

·  ломаная имеет с осью абсцисс только две общие точки – (0, 0) и (L, 0);

·  на ломаной лежит ровно L+1 целочисленная точка.

В рукописи указываются замеры – последовательность высот, в порядке прохождения горы слева направо. Известно, что замеры делались только в целочисленных точках. Расстояние между любыми двумя соседними замерами не менее 1 метра.

Так как, возможно, автор делал замеры не в каждой целочисленной точке, то однозначно восстановить профиль горы по записям в рукописи в общем случае невозможно.

Ваша задача найти количество возможных различных профилей горы, соответствующих найденной рукописи.

Формат входных данных

В первой строке записана тройка чисел H, L, K (1 £ H, L £ 40, 0 £ K £ L+1), где H – высота горы, L – длина горы, K – количество замеров. Во второй строке записано K целых чисел, каждое из которых соответствует высоте замера. Порядок соответствует движению слева направо.

Формат выходных данных

Выведите количество возможных различных профилей горы, соответствующих найденной рукописи.

Примеры

mountain. in	mountain. out
2 5 0	3
3 8 4 2 2 3 1	7
40 40 0	0

Пояснение

Для примера #1 возможные профили это:

_ / \ _/\ /\_ / \ / \ / \