Задание 19: первый шаг анализа игры

Самое лёгкое из трёх игровых заданий: ищем значение кучи, при котором выигрыш второго игрока виден на один ход вперёд.

Задание 19 почти всегда сводится к проверке «при любом ходе первого игрока второй выигрывает своим первым ходом».

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

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

Метод решения

Разбираем формулировку на проверяемые условия для позиции S:

Петя не выигрывает первым ходом: ни один ход из S не достигает порога. То есть НЕ win_in_1(S).
Ваня выигрывает первым своим ходом при любом ходе Пети: для КАЖДОГО хода Пети получившаяся позиция выигрышна за один ход (Ваня сразу добивает).

Перебираем все возможные S от 1 до порога и оставляем те, что подходят. Минимальное (или единственное) — ответ.

Разбор примера

Игра: одна куча, ходы «+1» и «×2», порог 49 (выигрывает достигший ≥ 49). Найдём S, при котором Петя не выигрывает первым ходом, но Ваня выигрывает своим первым при любой игре Пети.

Рассуждение: Петя из S может пойти в S+1 или 2S. Чтобы Петя не выиграл сразу, нужно S+1 < 49 и 2S < 49, то есть S ≤ 24. Чтобы Ваня после любого хода Пети добивал за ход, и S+1, и 2S должны быть «в одном шаге от 49». Проверим перебором.

Решение на Python

LIMIT = 49

def moves(s):
    return [s + 1, s * 2]

def win_in_1(s):
    # текущий игрок может одним ходом достичь порога
    return any(m >= LIMIT for m in moves(s))

answer = []
for s in range(1, LIMIT):
    if win_in_1(s):
        continue                       # Петя сам бы выиграл — не подходит
    # при ЛЮБОМ ходе Пети получившаяся позиция выигрышна за 1 ход (для Вани)
    if all(win_in_1(m) for m in moves(s)):
        answer.append(s)

print("Подходящие S (задание 19):", answer)

Вывод:

Подходящие S (задание 19): [24]

Единственное значение — 24. Проверим вручную: из 24 Петя ходит в 25 (24+1) или 48 (24·2). Из 25 Ваня может пойти в 50 ≥ 49 — победа. Из 48 Ваня идёт в 49 — победа. Петя сам из 24 не выигрывает (25 и 48 меньше 49). Условие выполнено.

Связь с таблицей проигрышных позиций

В предыдущем уроке мы нашли проигрышные позиции для ходящего: [1, 4, 6, 14, 16, 18, 20, 22, 24]. Число 24 — в этом списке: значит при S = 24 ходящий (Петя) проигрывает, выигрывает Ваня. Задание 19 просто требует, чтобы Ваня выигрывал именно первым своим ходом — самая «мелкая» проигрышная для Пети позиция у самого порога.

Как меняется ответ при других правилах

Конкретное число 24 зависит от правил. Поменяются ходы или порог — поменяется и ответ, но метод тот же: «Петя не добивает, Ваня добивает при любом ходе Пети». Универсальный код отделяет правила (функция moves и константа LIMIT) от логики анализа, поэтому под свой вариант достаточно поменять две строки. Покажем это: возьмём ходы «+2» и «×3», порог 30.

LIMIT = 30

def moves(s):
    return [s + 2, s * 3]      # другие правила — только эта строка

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

answer = [s for s in range(1, LIMIT)
          if (not win_in_1(s)) and all(win_in_1(m) for m in moves(s))]
print("Подходящие S при правилах +2 и x3, порог 30:", answer)

Вывод:

Подходящие S при правилах +2 и x3, порог 30: [8, 9]

При других правилах подходят уже два значения — 8 и 9, но строки анализа не изменились. Это и есть сила перебора: вы не выводите формулу заново для каждой игры, а лишь подставляете правила. На КЕГЭ это экономит время и исключает арифметические ошибки.

Два игрока и две кучи

Если в варианте две кучи, позиция — это пара чисел (a, b), а ходы применяются к одной из куч. Тогда moves((a, b)) возвращает все позиции-пары, достижимые за один ход, а условие конца — сумма куч ≥ порога. Логика win_in_1 и классификатора не меняется, просто позицией становится кортеж. Мемоизация lru_cache здесь обязательна — пар много.

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

Берут позицию, где Петя выигрывает сам. Сначала проверьте, что Петя НЕ выигрывает первым ходом, иначе условие нарушено.
Проверяют «существует ход», а нужно «при любом». Ваня должен добивать при ВСЕХ ходах Пети — это all(...), а не any(...).
Берут не то экстремальное значение. Если просят минимальное — берите наименьшее из подходящих; иногда подходящих несколько.

Итог

Задание 19 = «Петя не выигрывает за ход, но Ваня добивает при любом ходе Пети».
В коде: not win_in_1(S) и all(win_in_1(m) for m in moves(S)).
«При любом ходе» — это all; «существует ход» — это any; путаница здесь — главная ошибка.