ЕГЭ Инф. (19-21)

Универсальный шаблон

from functools import lru_cache

# 1. Глобальные настройки игры:
# limit = 41    — сумма камней, при достижении которой игра заканчивается
# grow = True   — направление игры (True: кучи растут >= limit, False: уменьшаются <= limit)
# error = False — условие № 19 (True: после неудачного хода Пети, False: при любом ходе Пети)
limit, grow, error = 41, False, True

# 2. Генерация стартовых партий:
# Храним пары (искомое число s, стартовый кортеж куч p).
# Для 2 куч достаточно заменить (s,) на (12,s), для 3 куч — на (5, 10, s).
games = [(s, (s,)) for s in range(42, 289)]


@lru_cache(None)  # Кэшируем результаты вызовов f(p, m, e), чтобы не считать позиции повторно
def f(p, m, e=False):
    # p — текущее состояние куч, например (12, 21)
    # m — сколько полуходов (шагов) осталось сделать до конца проверяемой ветки
    # e — допускается ли ошибка противника на текущем шаге (по умолчанию False)

    # Базовый случай 1: игра уже завершилась (порог limit достигнут).
    # Если m четное (0, 2, 4) — победный ход только что сделал НАШ игрок -> True.
    # Если m нечетное (1, 3) — победный ход только что сделал ПРОТИВНИК -> False.
    if (sum(p) >= limit if grow else sum(p) <= limit):
        return m % 2 == 0

    # Базовый случай 2: полуходы закончились (m == 0), а порог победы так и не достигнут -> False.
    if m == 0:
        return False

    # Генерация всех возможных следующих ходов из текущей позиции p:
    # i — индекс кучи (0 или 1), v — количество камней в ней.
    # x — новое число камней в выбранной куче после хода (+3 или *3).
    # Срез p[:i] + (x,) + p[i+1:] создает новый кортеж, где i-я куча заменена на x.
    # Аргумент e дальше не передаем (он автоматически станет False по умолчанию),
    # чтобы ошибка Пети в № 19 разрешалась только на его первом ходе.
    h = [f(p[:i] + (x,) + p[i+1:], m - 1)
         for i, v in enumerate(p) for x in (v -3, v -8, v//2)]

    # Оценка позиции (правило минимакса):
    # Нечетное m (1, 3) — сейчас ход НАШЕГО игрока: достаточно хотя бы одного победного хода -> any(h).
    # Четное m (2, 4) — сейчас ход ПРОТИВНИКА: нужно, чтобы ВСЕ его ходы вели к нашей победе -> all(h).
    # Исключение: если включен флаг ошибки (e=True), противник «поддается» -> срабатывает any(h).
    return any(h) if m % 2 or e else all(h)


# № 19: Ваня выигрывает своим 1-м ходом (m=2: ход Пети -> ход Вани).
# Распаковываем пару (s, p) и берем минимальное s.
print(19, min(s for s, p in games if f(p, 2, error)))

# № 20: Петя не может выиграть 1-м ходом (not f(p, 1)),
# но гарантированно выигрывает своим 2-м ходом (f(p, 3): П1 -> В1 -> П2).
# Срез [:2] берет два наименьших подходящих значения s.
print(20, [s for s, p in games if not f(p, 1) and f(p, 3)][:2])

# № 21: Ваня выигрывает 1-м или 2-м ходом при любой игре Пети (f(p, 4): П1 -> В1 -> П2 -> В2),
# но не имеет гарантированной победы сразу 1-м ходом (not f(p, 2)).
# Функция len() считает общее количество таких значений s.
print(21, len([s for s, p in games if not f(p, 2) and f(p, 4)]))

f.cache_clear()  # Очистка кэша (раскомментировать при смене правил игры в том же запуске)