Версия для печати
Убрать все задачи
Для игры «Отравленный пирог» используется прямоугольный пирог,
разделенный на M «строк» горизонтальными разрезами и на N «столбцов» –
вертикальными. Таким образом, пирог должен быть разбит на
M × N клеток, правая нижняя из которых «отравлена».
Играют двое игроков, ходы делаются по очереди. Каждый ход заключается
в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает
все клетки, расположенные левее и выше выбранной (в том числе и
выбранную). Проигрывает тот, кто съедает отравленную клетку.
Требуется написать программу, которая по заданной игровой позиции
определяет все возможные выигрышные ходы для начинающего в этой позиции.
Входные данные
Данные во входном файле расположены в следующем порядке: M, N
(1 ≤ M, N ≤ 9), X1, ..., XM. Здесь Xi
– число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами
и/или символами перевода строки.
Выходные данные
В первую строку выходного файла необходимо вывести количество различных
выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.
Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального
ряда, а j – номер (справа) вертикального ряда, которому принадлежит
выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).
Пример входного файла
3 5
5 4 3
Пример выходного файла
1
3 1
Решение
а) В группе из четырёх человек, говорящих на разных языках, любые трое могут общаться (возможно, один переводит двум другим).
Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.
б) То же для группы из 100 человек.
в) То же для группы из 102 человек.
Решение
Фильтр
