Разборы · ЕГЭ, задание 21

Задание 21 ЕГЭ по информатике: выигрышная стратегия второго игрока

Что проверяет задание

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

Что нужно знать

• Раз Ваня выигрывает при любой игре Пети, начальная позиция проигрышная для Пети: какой бы ход он ни сделал, Ваня отвечает выигрышной стратегией.
• «Первым или вторым ходом, но не гарантированно первым» — при лучшей игре Пети Ваня выигрывает именно вторым ходом. Петя, зная, что проиграет, тянет время.
• Удобно пользоваться той же функцией, что и в задании 20: для этого условия она должна вернуть −2.

Как решать

1. Напишите функцию game(a, b), которая возвращает +k или −k (см. разбор задания 20).
2. Найдите S, при которых game(17, S) = −2: ходящий (Петя) проигрывает, соперник (Ваня) выигрывает своим вторым ходом.
3. Выберите наименьшее (или то, что спрашивают).

Пример из демоверсии 2027

Игра та же, что в заданиях 19 и 20: кучи (17, S), ходы «+4» или «×2» к одной из куч, конец игры при сумме ≥ 133, первым ходит Петя. Найдите наименьшее S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, гарантирующей выигрыш первым ходом.

from functools import lru_cache

@lru_cache(None)
def game(a, b):
    # +k — ходящий выигрывает своим k-м ходом,
    # -k — ходящий проигрывает, соперник выигрывает своим k-м ходом
    moves = [(a + 4, b), (a * 2, b), (a, b + 4), (a, b * 2)]
    if any(x + y >= 133 for x, y in moves):
        return 1
    res = [game(x, y) for x, y in moves]
    lose = [-r for r in res if r < 0]
    return min(lose) + 1 if lose else -max(res)

print(min(S for S in range(1, 116) if game(17, S) == -2))      # 44

Ответ: 44.

Для контроля полезно вывести значения game(17, S) для всех S подряд: видно, где Петя выигрывает первым ходом (1), где вторым (2), где проигрывает (−1, −2). Например, при S = 56 и 57 значение −1: любой ход Пети даёт Ване выигрыш первым ходом. Первое S со значением −2 — как раз 44.

Решение на экзамене не проверяется — оценивается только ответ, поэтому программа здесь — законный и самый надёжный способ. Одна функция закрывает задания 20 и 21 и экономит время для заданий 26–27.

Типичные ошибки

• Путают −1 и −2: при −1 Ваня гарантированно выигрывает первым ходом, а это условие как раз исключено.
• Считают, что «выиграть первым или вторым ходом» — это просто «выиграть вторым»: надо учитывать, что Петя может сыграть плохо и Ваня выиграет раньше — это разрешено.
• Пишут функцию без lru_cache — перебор становится очень долгим.

Потренироваться: задание 21 новые варианты с проверкой ответа