Сапёр 1D

В этой задаче нужно угадать в каждой клетке первого ряда, находится ли там мина или нет. Нам понадобятся два ключевых утверждения:

  1. Мы всегда можем узнать, есть ли мина в третьей слева клетке и в третьей справа клетке;
  2. Если в некоторой клетке мы наверняка знаем, есть ли там мина или нет, то мы можем это узнать для клеток на $$$3$$$ позиции левее и правее.

Этого достаточно, чтобы решить случаи $$$N = 3k$$$ и $$$N = 3k + 1$$$. То есть, если $$$N$$$ при делении на $$$3$$$ даёт остаток $$$0$$$ или $$$1$$$, то мы можем решить любое поле Сапёра, и ответ равен $$$2^N$$$.

Если $$$N = 3k + 2$$$, то мы можем найти все мины в каждой третьей клетке, но этого недостаточно. Заметим, что если мы узнаем состояние ещё одной клетки, то это позволит решить головоломку. Посмотрим на все клетки, которые мы ещё не знаем: если две такие клетки подряд обе пустые или обе имеют мину, то мы сможем это определить, посмотрев на число под ними. Если же состояния неизвестных нам клеток чередуются, то мы не сможем решить головоломку; каждое число, которое мы откроем, будет указывать на две неизвестные клетки, и в них всегда будет в сумме $$$1$$$ мина.

Построим общий вид нерешаемой головоломки. В ней $$$N = 3k + 2$$$, то есть $$$N$$$ даёт остаток $$$2$$$ при делении на $$$3$$$. Каждая третья клетка может независимо друг от друга иметь или не иметь мину; всего $$$2^k$$$ вариантов. А все остальные клетки должны чередоваться, это дополнительный выбор из $$$2$$$ вариантов: начинаем с мины или с пустой клетки. Итого, если $$$N = 3k + 2$$$, то количество нерешаемых полей равно $$$2 \cdot 2^k$$$. Соответственно, количество решаемых полей равно $$$2^N - 2 \cdot 2^k$$$.

Так как ответ нужно вывести по модулю, рекомендуется использовать бинарное возведение в степень. Но $$$N$$$ небольшое, поэтому можно возвести в $$$N$$$-ю степень с помощью цикла.

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

Далее показаны два возможных расположения мин, которые могут быть на этом поле.