Question

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

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

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

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

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

Accepted Answer

97

Answer

Идея решения: построить две функции анализа позиций — одну для проверки выигрыша Вани за два его хода (ходы 1, 2, 3, 4, 5), другую для проверки выигрыша за один его ход (ходы 1, 2, 3), и найти значения $S$, удовлетворяющие обоим условиям. Функция `f(x, y, h)` определяет, может ли текущий игрок выиграть, если игра продолжается не более 5 ходов (два хода Вани): - При $h = 3$ или $h = 5$ (ходы Вани) и сумме $\ge 231$ — выигрыш. - При $h = 5$ и сумме $< 231$ — проигрыш. - При чётном $h$ (ход Пети) — проверяем, есть ли выигрывающий ход. - При нечётном $h$ (ход Вани) — проверяем, все ли ходы ведут к выигрышу. Функция `f1(x, y, h)` аналогична, но проверяет выигрыш за один ход Вани (ходы 1, 2, 3). ```python def f(x, y, h): if (h == 3 or h == 5) and x + y >= 231: return 1 elif h == 5 and x + y < 231: return 0 elif x + y >= 231 and h < 5: return 0 else: if h % 2 == 0: return (f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1)) else: return (f(x + 1, y, h + 1) and f(x, y + 1, h + 1) and f(x * 2, y, h + 1) and f(x, y * 2, h + 1)) def f1(x, y, h): if h == 3 and x + y >= 231: return 1 elif h == 3 and x + y < 231: return 0 elif x + y >= 231 and h < 3: return 0 else: if h % 2 == 0: return (f1(x + 1, y, h + 1) or f1(x, y + 1, h + 1) or f1(x * 2, y, h + 1) or f1(x, y * 2, h + 1)) else: return (f1(x + 1, y, h + 1) and f1(x, y + 1, h + 1) and f1(x * 2, y, h + 1) and f1(x, y * 2, h + 1)) result = [] for s in range(1, 214): if f(s, 17, 1) == 1 and f1(s, 17, 1) == 0: result.append(s) print(min(result)) ``` Перебираем все значения $S$ от 1 до 213. Для каждого значения проверяем: 1. Может ли Ваня выиграть за два своих хода (функция `f` возвращает 1). 2. Не может ли Ваня выиграть за один ход (функция `f1` возвращает 0). Минимальное значение, удовлетворяющее обоим условиям, — это ответ.

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