Question

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

Например, позицию (20, 30) можно преобразовать в любую из четырёх позиций: (24, 30), (20, 34), (60, 30), (20, 90).

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

В начальный момент в первой куче 11 камней, во второй куче — $S$ камней; $1 \le S \le 142$.

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

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение $S$, при котором такая ситуация возможна.

Accepted Answer

16

Answer

Идея решения: используем рекурсивный анализ позиций с отслеживанием номера хода — позиция выигрышна для текущего игрока, если он может сделать ход в позицию, где сумма $\ge 154$, или в позицию, проигрышную для противника. Обозначим позицию как $(x, y, h)$, где $x$ и $y$ — количества камней в кучах, $h$ — номер хода (1 — Петя, 2 — Ваня, 3 — Петя и т. д.). Функция `f(x, y, h)` возвращает 1, если текущий игрок может выиграть из позиции $(x, y)$ на ходу $h$, и 0 иначе. **Базовые случаи:** - Если $h = 3$ (Петя делает второй ход) и $x + y \ge 154$, то Ваня уже выиграл на своём первом ходе — возвращаем 1. - Если $h = 3$ и $x + y < 154$, то Ваня не выиграл — возвращаем 0. - Если $x + y \ge 154$ и $h < 3$, то текущий игрок уже выиграл, но это не соответствует условию (Ваня выигрывает первым ходом) — возвращаем 0. **Рекурсивный случай:** Из позиции $(x, y)$ можно перейти в четыре позиции: $(x+4, y)$, $(x, y+4)$, $(3x, y)$, $(3x, y)$. Текущий игрок выигрывает, если хотя бы один из этих ходов ведёт в выигрышную позицию для него. Ищем минимальное $S$ такое, что Петя (первый ход) может попасть в позицию, где Ваня выигрывает своим первым ходом. ```python def f(x, y, h): if h == 3 and x + y >= 154: return 1 elif h == 3 and x + y < 154: return 0 elif x + y >= 154 and h < 3: return 0 else: return (f(x + 4, y, h + 1) or f(x, y + 4, h + 1) or f(x * 3, y, h + 1) or f(x, y * 3, h + 1)) for s in range(1, 143): if f(11, s, 1) == 1: print(s) break ``` Проверим несколько значений: - $S = 15$: $(11, 15) o$ Петя может сделать ход, но ни один не приводит к выигрышу Вани на его первом ходе. - $S = 16$: $(11, 16) o$ Петя может добавить 4 в первую кучу: $(15, 16)$, сумма = 31. Ваня может утроить вторую кучу: $(15, 48)$, сумма = 63. Или Ваня может утроить первую: $(45, 16)$, сумма = 61. Продолжая анализ, находим, что Ваня может выиграть первым ходом.

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