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

Просмотров 9 Комментарии 0

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

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

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

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

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

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 ’WIN1’
    elif any(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’

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

Ответ: 5