printЗанятие 15

printC. Датская игра

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

629.jpg
В старой датской игре, положившей начало современной игре в кегли, в ряд располагаются `N` деревянных кеглей. Одним ударом шара можно сбить либо одну, либо две соседних кегли. Для того чтобы это сделать, не требуется много умения. Игроки бросают поочередно шар, а цель игры состоит в том, чтобы сбить последнюю кеглю.
Горный гном, с которым Рип ван Винкль играет эту партию, только что сбил кеглю №2. Рип должен выбрать одну из 22 возможностей: сбить одну из 12 кеглей или метнуть шар в один из 10 промежутков между кеглями, чтобы сбить пару соседних кеглей. Напишите программу, вычисляющую для любой текущей ситуации в игре наилучший ход, чтобы Рип мог выиграть партию. Предполагается, что оба игрока действуют наилучшим образом.
В первой строке ввода содержится одно целое число `N\ (1\ ≤\ N\ ≤\ 100)` – количество оставшихся кеглей. В следующей строке содержится N различных целых чисел от 1 до 100 в порядке возрастания – номера оставшихся кеглей. Соседние кегли имеют номера, отличающиеся на 1.
В первой строке входного файла вывести либо 0, если у игрока нет выигрышного хода, либо 1 или 2 – количество сбиваемых кеглей. Во второй строке вывести их номера через пробел. Если существует несколько вариантов – вывести вариант с наименьшим номером кегли.

Пример ввода

12
1 3 4 5 6 7 8 9 10 11 12 13

Пример вывода

1
6
использована головоломка Сэма Лойда
loading