Номер 19-21. Разбор по информатике

Два игрока, Петя и Ваня, играют в следующую игру: перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавлять камни в кучу, убирать камни или изменять количество камней в куче. Игра завершается при достижении определённого количества камней.

Задача 1 (8192) из ЕГКР-2025:

- Ходы: +2, +5, ×2
- Цель: не менее 128
- Вопрос 1: минимальное S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выграть своим первым ходом
- Вопрос 2: два наименьших S, когда Петя имеет выигрышную стратегию, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом
- Вопрос 3: минимальное S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети

Решение — рекурсивная функция g(s, p):

```python
def g(s, p):
if s >= 128:
return p % 2 == 0
moves = [g(s+2, p+1), g(s+5, p+1), g(s*2, p+1)]
return any(moves) if p % 2 == 1 else all(moves)
```

- Для Пети (нечётный ход) — any (достаточно одного выигрышного хода)
- Для Вани (чётный ход) — all (все ходы должны сохранять возможность выигрыша)

Ответы: 62 (Ваня выигрывает первым ходом), 31 57 (Петя выигрывает вторым ходом), 55 (Ваня выигрывает первым или вторым)