Задание 21 ЕГЭ: одна куча, камни добавляются

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

Пример

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• добавить в кучу один камень;
• добавить в кучу пять камней;
• увеличить количество камней в куче в три раза.

Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 15 или 30 камней.

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 94. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в куче будет 94 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 93.

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

Найдите наименьшее значение S, при котором одновременно выполняются два условия:

• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Первое условие — f(S, 4): при любой игре Пети Ваня выигрывает не позже своего второго хода. Второе — не f(S, 2): гарантированно выиграть первым ходом Ваня не может (иначе это значение S из задания 19). Нужны S, для которых верно первое и не верно второе.

Проверка для S = 25 (все ходы Пети):

Петя: 26 — одним ходом Ване не выиграть; он ходит в 31, и после любого хода Пети выигрывает своим вторым ходом.
Петя: 30 — одним ходом Ване не выиграть; он ходит в 31, и после любого хода Пети выигрывает своим вторым ходом.
Петя: 75 — Ваня сразу выигрывает ходом в 225.

Программа: f(p, m) — может ли «наш» игрок выиграть из позиции p не более чем за m полуходов (на нечётном m ходит «наш» игрок — нужен хотя бы один хороший ход, any; на чётном ходит соперник — хорошими должны быть все его ходы, all).

from functools import lru_cache


def moves(x):
    return [x + 1, x + 5, x * 3]


def done(x):
    return x >= 94


@lru_cache(None)
def f(p, m):
    if done(p):
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(q, m - 1) for q in moves(p)]
    return any(h) if m % 2 else all(h)


R = range(1, 94)
print(min(s for s in R if f(s, 4) and not f(s, 2)))

Ответ: 25.

Решить такую задачу — новый вариант с проверкой