3 Что надо знать для решения

Что надо знать для решения

Как устроена игра

Во всех задачах одинаковая рамка:

  • Есть куча (или две) камней. В начале в ней S камней — это и есть то, что мы ищем.

  • Игроки ходят по очереди, первым ходит Петя.

  • За один ход можно применить одну из нескольких операций (прибавить, умножить, вычесть, поделить — что дано в условии).

  • Игра заканчивается, когда камней стало не меньше (в «растущих» играх) или не больше (в «убывающих») порога.

  • Побеждает тот, кто сделал последний ход — перешагнул границу.

Ключевые слова: кто и когда выигрывает

Весь блок 19–21 крутится вокруг четырёх типовых ситуаций. Разберись с ними один раз — и дальше просто узнаёшь их в условии:

  • «Выиграть за один ход» — из позиции S можно одним ходом перешагнуть границу.

  • «При любом ходе Пети Ваня выигрывает первым ходом» — что бы Петя ни сделал, Ваня следующим ходом финиширует. Это позиция, где выигрывает второй игрок сразу. Основа задания 19.

  • «Петя выигрывает вторым ходом» — у Пети есть такой первый ход, что при любом ответе Вани Петя добивает вторым ходом. Основа задания 20.

  • «Ваня выигрывает вторым ходом» — что бы Петя ни сделал, Ваня добивает не позже своего второго хода. Основа задания 21.

Дерево игры и минимакс «на пальцах»

Представь все ходы в виде дерева: корень — стартовая позиция, из каждой позиции ветки — возможные ходы. Игроки чередуются по уровням.

Оцениваем позиции с конца (это называется минимакс):

  • Если ходит тот, кто хочет выиграть (мы) — ему достаточно хотя бы одного хорошего хода. Значит, соединяем ветки через «ИЛИ» → в Python это any.

  • Если ходит соперник (он нам вредит) — нам нужно, чтобы любой его ход всё равно вёл к нашей победе. Значит, соединяем через «И» → в Python это all.

Вот и вся теория игр для ЕГЭ: чередуем any (наш ход) и all (ход соперника), пока не дойдём до финиша.

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

Открываешь чистый файл — сразу набивай этот скелет. Он решает все три задания для игры с одной кучей.

def F(s, p):                          # s — камней в куче, p — на сколько ходов смотрим вперёд
    if s >= 51:                       # игра закончилась (порог из условия!)
        return p % 2 == 0             # чётное p — победил тот, кто хотел; нечётное — соперник
    if p == 0:                        # ходы кончились, а финиша нет
        return False                  # значит, за столько ходов не выиграть
    hod = [F(s + 1, p - 1),           # перебираем ходы ИЗ УСЛОВИЯ:
           F(s + 4, p - 1),           #   +1, +4
           F(s * 2, p - 1)]           #   и ×2
    if p % 2 == 1:                    # нечётное p — сейчас ход того, кто хочет выиграть
        return any(hod)               #   достаточно ОДНОГО хорошего хода
    else:                             # чётное p — ход соперника
        return all(hod)               #   нужно, чтобы ЛЮБОЙ вёл к победе

Что означает p — это глубина, «за сколько ходов смотрим вперёд». А теперь главное — как из этой функции получить ответы на 19, 20 и 21.

Таблица «вопрос → вызов функции»

Это сердце всего блока. Запомни как таблицу умножения:

Что спрашивают

Как проверить

Смысл

Петя выигрывает за один ход

F(S, 1)

есть ход, сразу дающий финиш

19: при любом ходе Пети Ваня выигрывает 1-м ходом

F(S, 2)

что бы Петя ни сделал — Ваня добьёт

20: Петя выигрывает своим 2-м ходом

F(S, 3) and not F(S, 1)

Петя добьёт вторым, но не первым

21: Ваня выигрывает своим 2-м ходом

F(S, 4) and not F(S, 2)

Ваня добьёт вторым, но не гарантированно первым

Читается по чётности p:

  • `F(S, 1)` (нечётное) — «есть ли у Пети ход, дающий финиш прямо сейчас».

  • `F(S, 2)` (чётное) — «правда ли, что при любом ходе Пети у Вани найдётся добивающий ход». Это ровно задание 19.

  • `F(S, 3)` (нечётное) — «есть ли у Пети ход, после которого при любом ответе Вани Петя добьёт». Задание 20 (плюс not F(S,1), чтобы это был именно второй ход, а не первый).

  • `F(S, 4)` (чётное) — «правда ли, что при любом ходе Пети Ваня добьёт вторым». Задание 21 (плюс not F(S,2), чтобы Ваня не выигрывал уже первым ходом).

📌 Как перебрать все S сразу

Чтобы не подставлять значения вручную, гоняем весь диапазон из условия одной строкой и печатаем все подходящие S:

print([S for S in range(1, 51) if F(S, 2)]) # все позиции задания 19

Дальше берёшь из списка то, что просят: минимальное, два наименьших или наименьшее из нескольких — смотри по условию конкретного прототипа.

Приём для «неудачного хода» — `any` у проигрывающего

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

Это уже не «при любом ходе Пети». Это «существует неудачный (то есть какой-то один плохой) ход Пети, после которого Ваня добивает». Ключевое слово — «существует».

Приём простой: у проигрывающего игрока (тут это Петя) на его ходу меняем all на `any`. Было «при любом ходе Пети», стало «есть неудачный ход Пети». Всё остальное — та же функция.

# Обычная задача 19:  ... at любой ход Пети → all(hod)
# «Неудачный ход»:     ... есть ход Пети   → any(hod)

Разберём это подробно ниже, в задании 4 — там как раз такая формулировка.

Универсальный шаблон для ДВУХ куч

Если в условии две кучи (a, b) — функция та же, просто ходов больше и аргументов два:

def F(a, b, p):                       # две кучи: a и b камней
    if a + b >= 81:                   # игра закончилась (сумма достигла порога)
        return p % 2 == 0
    if p == 0:
        return False
    hod = [F(a + 1, b, p - 1),        # +1 в первую кучу
           F(a * 2, b, p - 1),        # ×2 первую кучу
           F(a, b + 1, p - 1),        # +1 во вторую кучу
           F(a, b * 2, p - 1)]        # ×2 вторую кучу
    return any(hod) if p % 2 == 1 else all(hod)