Question

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 129 или больше камней.

В начальный момент в куче было *S* камней, $1 \leq S \leq 128$.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите минимальное значение *S*, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений *S*, в ответе запишите минимальное из них.

Accepted Answer

62

Answer

Идея решения: найти позиции, из которых Ваня (второй игрок) гарантирует победу за два своих хода, но не может выиграть за один ход.

Используем рекурсивный анализ с мемоизацией. Функция `f(s, t, L, d)` определяет исход игры:
- `s` — текущее количество камней;
- `t` — целевое значение (129);
- `L` — номер хода (0 — ход Пети, 1 — ход Вани, и т. д.);
- `d` — максимальная глубина (количество ходов для анализа).

Функция возвращает:
- `1` — выигрыш для игрока, чей ход на уровне 0 (Пети);
- `-1` — выигрыш для противника (Вани);
- `0` — неопределённый результат (глубина исчерпана).

Логика:
- Если $s \geq 129$, игрок, сделавший ход, выиграл. Возвращаем `1` для чётного хода (Петя), `-1` для нечётного (Ваня).
- Если глубина исчерпана, возвращаем `0`.
- На ходу Пети (чётный номер) выбираем максимум (он хочет выиграть).
- На ходу Вани (нечётный номер) выбираем минимум (он хочет, чтобы Петя проиграл).

Условия для ответа:
- `f(s, 129, 0, 4) == -1` — Ваня выигрывает за два своих хода (4 хода всего);
- `f(s, 129, 0, 2) != -1` — Ваня не может гарантировать победу за один свой ход (2 хода всего).

```python
def f(s, t, L, d):
    if s >= t:
        return -1 if L % 2 == 1 else 1
    elif L > d:
        return 0
    else:
        r1 = f(s + 1, t, L + 1, d)
        r2 = f(s * 2, t, L + 1, d)
        if L % 2 == 0:
            return max(r1, r2)
        else:
            return min(r1, r2)

for s in range(1, 129):
    if f(s, 129, 0, 4) == -1 and f(s, 129, 0, 2) != -1:
        print(s)
        break
```

Проверим логику для $S = 62$:
- Петя может сделать ход: $62 + 1 = 63$ или $62 	imes 2 = 124$.
- Если Петя выбирает 124, Ваня удваивает: $124 	imes 2 = 248 \geq 129$ — Ваня выигрывает первым ходом.
- Если Петя выбирает 63, Ваня добавляет 1: $63 + 1 = 64$. Затем:
  - Если Петя выбирает 65, Ваня удваивает: $65 	imes 2 = 130 \geq 129$ — Ваня выигрывает.
  - Если Петя выбирает 128, Ваня добавляет 1: $128 + 1 = 129$ — Ваня выигрывает.

Таким образом, при $S = 62$ Ваня гарантирует победу за два своих хода. При этом из позиции 62 Ваня не может выиграть первым ходом (так как после первого хода Пети позиция становится либо 63, либо 124, и только из 124 Ваня выигрывает сразу).

Задание №21Алгоритмы и исполнителиЕГЭ по информатике