Программирование игровой стратегии на Python (задание 21)

Зачем это в ЕГЭ. Задание 21 проверяет умение анализировать и оптимизировать алгоритмы. Даёт 2 первичных балла. Встречается в 90% вариантов, требует понимания циклов, условий и структур данных.

Главная идея. Нужно найти оптимальную стратегию для игрока, максимизирующую выигрыш. Ключ — моделирование ходов и анализ дерева решений. Часто используется рекурсия или динамическое программирование.

Алгоритм (чеклист).
1. Определить правила игры и условия победы
2. Построить дерево возможных ходов
3. Для каждой позиции вычислить выигрышную стратегию
4. Найти минимальное количество ходов для победы
5. Проверить крайние случаи (начало и конец игры)

Опоры (кратко).
- Формула минимального выигрышного хода: $k = \lceil \frac{N}{max\_step} \rceil$
- Рекуррентное соотношение для динамического программирования: $dp[i] = \lor (\neg dp[i - s])$ для всех допустимых шагов $s$
- Инвариант: если $N \mod (max\_step + min\_step) == 0$, то второй игрок может выиграть

Пример 1 (минимальное количество ходов).
Шаг 1. Дано: куча из 20 камней, за ход можно взять 1, 2 или 3 камня.
Шаг 2. Выигрывает тот, кто возьмёт последний камень.
Шаг 3. Оптимальная стратегия: оставлять противнику кратное 4 камня.
Шаг 4. Первый игрок берёт 20 % 4 = 0 → берёт 3 (оставляет 17).
Шаг 5. Второй берёт $x$, первый берёт (4 - $x$).
Шаг 6. Итог: первый игрок выигрывает за 7 ходов.

Пример 2 (динамическое программирование).
Шаг 1. Дано: куча из $N$ камней, ходы +1, +2, *3.
Шаг 2. Выигрыш — первым достичь ≥ 100.
Шаг 3. Создаём массив dp[0..100], где dp[i] = может ли текущий игрок выиграть из позиции i.
Шаг 4. База: dp[100..] = True.
Шаг 5. Рекурсия: dp[i] = not (dp[i+1] and dp[i+2] and dp[i*3]).
Шаг 6. Ответ: все i, из которых можно выиграть за 1 ход.

Типичные ошибки.
1. Неправильный базовый случай — забывают проверить условия победы
2. Неоптимальная стратегия — выбирают локально максимальный ход вместо глобально оптимального
3. Переполнение стека — не ограничивают рекурсию при больших N
4. Неправильный инвариант — ошибаются в выборе ключевого модуля для выигрышной стратегии
5. Не учитывают все ходы — пропускают один из возможных вариантов хода

Дальше. Решайте задачи на рекурсивные стратегии и динамическое программирование из банка ФИПИ.