ЕГЭ по информатике 2026, задание 20: выигрышная стратегия

Задание 20 — повышенный уровень, 1 балл, та же игра, что в №19. Обычно просят два наименьших S, при которых Петя имеет выигрышную стратегию, причём не быстрее своего второго хода. Ответ — два числа в порядке возрастания, без лишних знаков.

Частичного балла нет. Оба числа и порядок должны совпасть с эталоном.

Конспект

Победа своим вторым ходом означает:

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

Это не «Петя может выиграть, если Ваня ошибётся». Стратегия учитывает любой ход проигрывающего. ФИПИ пишет, что главная ошибка блока 19–21 — разобрать не все ходы того, кто проигрывает при правильной стратегии.

Порядок разметки:

1. Отметьте позиции победы за 1 ход, как в задании 19.

2. Позиция проигрыша за 1 ход соперника: сама не выигрышная за 1, и каждый ход из неё ведёт в победу за 1.

3. Победа за 2 хода: есть ход в позицию проигрыша соперника, и нет победы за 1.

Для двух куч считайте сумму, если в ответе сумма, и не выводите обе кучи, если бланк ждёт два значения S.

Если подходящих S больше двух, берут два наименьших, если так сказано. Не выводите все.

Шаблон на Python

GOAL = 129

def moves(s):
    return [x for x in (s + 1, s * 2) if x < 300]

def win_in_1(s):
    return any(m >= GOAL for m in moves(s))

def lose_in_1(s):
    if s >= GOAL or win_in_1(s):
        return False
    return all(win_in_1(m) for m in moves(s))

def win_in_2(s):
    if s >= GOAL or win_in_1(s):
        return False
    return any(lose_in_1(m) for m in moves(s))

ans = [s for s in range(1, GOAL) if win_in_2(s)]
print(*ans[:2])

Ограничение x < 300 не должно отрезать ход, который ещё имеет смысл. Если после умножения получается значение больше цели, оно как раз выигрышное и должно попасть в список ходов. Фильтруйте только совсем далёкие ветки, которые правилами запрещены.

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

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