18-ая Белорусская республиканская олимпиада по информатике.
2005 год. г.Витебск.
1 тур.

1. Перетягивание каната
Для участия в соревнованиях по перетягиванию каната зарегистрировалось N человек. Некоторые из участников могут быть знакомы друг с другом. Причем, если двое из них имеют общего знакомого, то это не означает, что они обязательно знакомы друг с другом.
Организаторы соревнований заинтересованы в их качественном проведении. Они хотят разделить всех участников на две команды так, чтобы в первой команде было K человек, а во второй – N-K человек. Из всех возможных вариантов формирования команд, организаторы хотят выбрать такой вариант, при котором сумма сплоченностей обеих команд максимальна. Сплоченностью команды называется количество пар участников этой команды, знакомых друг с другом. Ваша задача – помочь организаторам найти требуемое разделение участников на две команды.
Формат входных данных:
В первой строке входного файла задаются три числа N, K, M, разделенные одиночными пробелами, где N – общее число зарегистрированных участников, K – требуемое количество человек в первой команде, M – количество пар участников, знакомых друг с другом.
Каждая из следующих M строк содержит два различных числа, разделенные пробелом – номера двух участников, знакомых друг с другом. Все участники нумеруются от 1 до N.
Ограничения:
Все числа целые
0 < K < N < 25
0 <= M <= N(N-1)/2
Формат выходных данных:
Выходной файл должен содержать одну строку, состоящую из K чисел, каждое из которых задает номер участника, попавшего в первую команду. Числа должны быть разделены пробелами. Если существует несколько решений данной задачи, то выведите любое из них.

Пример входных данных:
5 3 3
1 3
2 5
5 4
Пример выходных данных:
5 2 4

2. Контрольная работа
Петя для выполнения контрольной работы по математике аккуратно вырезал из бумаги в клеточку лист прямоугольной формы размером N клеток по вертикали и M клеток по горизонтали.
Перед уроком, в ожидании учителя, чтобы как-нибудь развлечься, Петя раскрасил ручкой на листе бумаги K различных клеток. Получив замечание учителя, Петя решил вырезать из этого листа бумаги меньший прямоугольный листок, на котором не было бы раскрашенных клеток, и сказал учителю, что знает сколькими различными способами это можно сделать.
Петя считает, что два способа вырезания прямоугольных листков являются различными, если на листе бумаги найдется хотя бы одна клетка, которая принадлежит одному из вырезаемых листков и не принадлежит другому.
На самом деле, Петя не знает точного числа всевозможных способов вырезания листка прямоугольной формы. Однако он слышал о больших возможностях современных вычислительных машин, поэтому решил попросить помощи у участников республиканской олимпиады по информатике.
Производить разрезы разрешается только по линиям, разделяющим клетки друг от друга.
Формат входных данных:
В первой строке входного файла находятся три числа N, M и K, разделенные пробелами, где N и M – размеры листа бумаги, а K – количество закрашенных Петей клеток. Каждая из следующих K строк содержит два числа, разделенные пробелом и описывающие одну закрашенную клетку. Первое число определяет номер строки листа бумаги, в которой находится закрашенная клетка, а второе число – номер столбца. Строки листа бумаги нумеруются сверху вниз от 1 до N, а столбцы – слева направо от 1 до M.
Ограничения:
Все числа натуральные
1 <= N, M <= 5000
1 <= K <= 100000
1 <= K < NM

Формат выходных данных:
Выходной файл должен состоять из одной строки, содержащей одно целое число, равное количеству способов, которыми можно вырезать прямоугольный листок, не содержащий раскрашенных клеток, из испорченного Петей листа бумаги.
Пример входных данных:
4 3 3
1 2
4 3
3 1
Пример выходных данных:
22

3. Кликомания
Кликомания – это игра для одного игрока. Для игры требуется прямоугольное поле, разделенное горизонтальными и вертикальными линиями на N строк и M столбцов. Каждая клетка поля раскрашена в один из K цветов. На поле введена координатная система, в соответствии с которой каждая клетка характектеризуется двумя координатами. Первая координата – это номер столбца, в котором находится клетка, а вторая координата – это номер строки. Столбцы нумеруются слева направо от 1 до M. Строки нумеруются снизу вверх от 1 до N.
Две клетки поля называются соседними, если они имеют общую сторону.
Путем между двумя клетками A и B, раскрашенными в один цвет, называется последовательность клеток, раскрашенных в тот же цвет, что A и B, причем первой клеткой последовательности является клетка A, последней – клетка B, и любые две клетки, стоящие рядом в последовательности, являются соседними.
Набор клеток называется связным, если между его любыми двумя клетками существует хотя бы один путь.
Набор клеток называется блоком, если он является связным и добавление к нему любой клетки поля, не принадлежащей этому набору, приводит к тому, что он перестает быть связным. Мощностью блока называется количество клеток в нем.
За один ход игрок может удалить с поля все клетки любого блока, мощность которого больше единицы.
Для понимания того, что происходит дальше, представьте себе, что удаленные клетки заменены на пустое пространство, и на игровом поле действует гравитация. Это означает, что некоторые клетки или группы клеток могут оказаться «висящими в воздухе» и гравитация заставляет их падать вертикально вниз.
Более точно данный процесс может быть описан следующим образом: пока на поле есть хотя бы одна клетка, непосредственно снизу от которой находится пустое пространство, любая из таких клеток перемещается на одну позицию вниз. При этом предполагается, что поле ограничено по краям, так что непосредственно снизу от любой клетки из самой нижней строки находится не пустое пространство, а граница поля. Далее происходит еще одна модификация поля: пока на поле есть хотя бы один пустой столбец, то есть столбец, не содержащий раскрашенных клеток, все клетки правее любого из таких столбцов сдвигаются на одну позицию влево.
После этого игрок может делать следующий ход.
Каждый раз, когда игрок удаляет блок мощности P, он получает очков. Игра продолжается до тех пор, пока игрок может сделать какой-либо ход. Другими словами, игра заканчивается, когда либо все клетки удалены с поля, либо любой блок на поле имеет мощность, равную единице. Цель игрока – максимизировать количество набранных очков по окончанию игры.
Вам предоставляются 10 входных файлов input1.txt, input2.txt, …, input10.txt, каждый из которых содержит описание поля для игры в Кликоманию. Вам необходимо сдать на проверку 10 выходных файлов output1.txt, output2.txt, …, output10.txt. Выходной файл outputX.txt должен содержать описание игры в Кликоманию, сыгранной на поле, заданном во входном файле inputX.txt. Для получения выходных файлов Вы можете писать произвольные программы, однако эти программы не нужно сдавать на проверку – нужно сдать только выходные файлы. За каждый сданный выходной файл Вы получите определенное количество баллов.
Формат входных данных:
Первая строка входного файла содержит три числа N, M, K, разделенные одиночными пробелами, где N и M – размеры игрового поля, а K – количество используемых цветов. Каждая из следующих N строк файла описывает одну строку игрового поля и содержит ровно M символов; j-й символ в i-й из этих строк описывает цвет клетки поля, имеющей координаты (j, ). Цвета клеток задаются цифрами от 1 до K.
Ограничения:
1 <= N, M <= 50
1 < K <= 5
Формат выходных данных:
Первая строка выходного файла содержит целое число Q, равное количеству сделанных ходов. Далее выведите Q строк, содержащих описания самих ходов. Каждая из этих строк должна описывать один ход и содержать координаты любой клетки из удаляемого на этом ходу блока, разделенные одним пробелом. Вывод описаний ходов осуществляется в том порядке, в котором эти ходы делаются во время игры.
Оценка
За каждый сданный выходной файл Вы получите некоторое количество баллов. Если сданный Вами выходной файл имеет неправильный формат, то Вы получите 0 баллов. Если описание игры в сданном Вами файле противоречит правилам игры или является неполным, то есть игра не доиграна до конца, то Вы также получите 0 баллов. В противном случае Ваш балл будет вычисляться по формуле , где S – количество набранных Вами очков, а Best – наибольшее количество очков в корректных выходных файлах для данного входного файла, сданных всеми участниками. Баллы за каждый выходной файл округляются вверх до десятых и суммируются. Сумма, округленная вверх до ближайшего целого, составляет Ваш балл за задачу.

Пример входных данных:
6 4 3
1131
1311
2212
1311
3231
3331
Пример выходных данных:
4
2 4
4 1
3 1
2 1