Задача к ЕГЭ по информатике на тему «прочие прототипы» №2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано двоичное число. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может приписать справа или слева к имеющемуся на листе числу двоичную запись любого из чисел вида $22n + 1$ , где $n$ — произвольное натуральное число, либо приписать справа и слева от имеющегося на листе числа его копию. Например, имея двоичное число $11001$ , за один ход можно получить путём копирования число $110011100111001$ или путём приписывания двоичной записи числа $5$ числа $10111001$ или $11001101$ .

Игра завершается в тот момент, когда количество единиц в двоичной записи числа на листе станет больше или равно $42$ . Победителем считается игрок, сделавший последний ход, т. е. первым получивший двоичное число, в записи которого использовано $42$ или более единиц.

В начальный момент единиц в числе было $S(1 ≤ S ≤ 41)$ .

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$ , когда такая ситуация возможна.

Решение руками

Эта задача легко сводится к куче камней. За один ход можно добавить к куче $2$ камня, ведь любое число, имеющее вид $22n + 1$ имеет лишь $2$ единицы, либо умножить количество камней в куче на $3$ . Тогда очевидно, что первым ходом Петя утроил количество камней, после чего Ваня сделал то же самое. Значит нам подойдёт значение $S = 5.$

Решение программой

from functools import lru_cache


def moves(heap):
    return heap + 2, heap * 3


@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 41):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 5