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.
Таблица «вопрос → вызов функции»
Это сердце всего блока. Запомни как таблицу умножения:
Что спрашивают | Как проверить | Смысл |
|---|---|---|
Петя выигрывает за один ход |
| есть ход, сразу дающий финиш |
19: при любом ходе Пети Ваня выигрывает 1-м ходом |
| что бы Петя ни сделал — Ваня добьёт |
20: Петя выигрывает своим 2-м ходом |
| Петя добьёт вторым, но не первым |
21: Ваня выигрывает своим 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:
Дальше берёшь из списка то, что просят: минимальное, два наименьших или наименьшее из нескольких — смотри по условию конкретного прототипа. |
Приём для «неудачного хода» — `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)