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

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

Пример

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

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

Например, имея кучу из 118 камней, за один ход можно получить кучу из 117 или 39 камней.

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

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

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

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания через пробел.

Решение

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

Подходят S = 181, 540, 541, 542. Спрашивают не два наименьших, а наименьшее и наибольшее — первый и последний элементы списка, поэтому диапазон просматриваем до конца.

Проверка для S = 181: выиграть первым ходом Петя не может, а ходом 181 → 180 он ставит Ваню в проигрышную позицию: любой ход Вани (слева) Петя заканчивает выигрышным ходом (справа):

179 → 59
60 → 59

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

from functools import lru_cache


def moves(x):
    return [x - 1, x // 3]


def done(x):
    return x <= 59


@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(60, 2000)    # верхней границы у S нет — берём с запасом
a20 = [s for s in R if f(s, 3) and not f(s, 1)]
print(a20[0], a20[-1])

Ответ: 181 542.

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