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

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

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

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

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

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

Как решать

Удобнее всего написать одну функцию для всех трёх заданий. Она возвращает +k, если ходящий игрок выигрывает своим k-м ходом (при лучшей игре обеих сторон), и −k, если он проигрывает, а соперник выигрывает своим k-м ходом. Выигрывающий игрок старается закончить быстрее, проигрывающий — затянуть игру.

1. Если есть ход, сразу заканчивающий игру, — результат 1.
2. Иначе смотрим результаты всех ходов (для соперника). Если есть ходы, после которых соперник проигрывает, выбираем самый быстрый выигрыш: min + 1.
3. Если таких ходов нет, мы проигрываем и затягиваем игру: −max.

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

Игра та же, что в задании 19: кучи (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([S for S in range(1, 116) if game(17, S) == 2][:2])      # [28, 48]

Значение 2 означает ровно то, что спрашивают: Петя выигрывает, но не первым ходом, а вторым. Ответ: 28 48.

Проверим одно значение вручную. При S = 28 Петя первым ходом выиграть не может: максимум — удвоение второй кучи, 17 + 56 = 73. Этот ход и есть выигрышный: из (17, 56) Ваня получает (21, 56), (34, 56), (17, 60) или (17, 112) — сумма везде меньше 133. В первых трёх случаях Петя удваивает вторую кучу (21 + 112, 34 + 112, 17 + 120), в последнем добавляет 4 камня (17 + 116) — и выигрывает вторым ходом.

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

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

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