Question

Для игры, описанной в задании 19, найдите **минимальное** значение $S$, при котором одновременно выполняются два условия:

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

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

Accepted Answer

24

Answer

Идея решения: найти минимальное начальное значение, при котором Ваня гарантирует победу за два хода, но не может выиграть за один ход. Используем рекурсивный анализ позиций с мемоизацией. Определим две функции: 1. `f(x, h)` — проверяет, может ли текущий игрок выиграть за два хода Вани (глубина поиска до 5 ходов). 2. `f1(x, h)` — проверяет, может ли текущий игрок выиграть за один ход Вани (глубина поиска до 3 ходов). Условие победы: достижение значения $\geq 88$. На чётных ходах (ход Вани) ищем выигрышный ход (логический OR по всем возможным ходам). На нечётных ходах (ход Пети) проверяем, что все его ходы ведут к проигрышу для Вани (логический AND). ```python def f(x, h): if (h == 3 or h == 5) and x >= 88: return 1 elif h == 5 and x < 88: return 0 elif x >= 88 and h < 5: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 3, h + 1)) else: return (f(x + 1, h + 1) and f(x + 4, h + 1) and f(x * 3, h + 1)) def f1(x, h): if h == 3 and x >= 88: return 1 elif h == 3 and x < 88: return 0 elif x >= 88 and h < 3: return 0 else: if h % 2 == 0: return (f1(x + 1, h + 1) or f1(x + 4, h + 1) or f1(x * 3, h + 1)) else: return (f1(x + 1, h + 1) and f1(x + 4, h + 1) and f1(x * 3, h + 1)) # Позиции, где Ваня выигрывает за два хода winning_two = [] for x in range(1, 88): if f(x, 1) == 1: winning_two.append(x) # Позиции, где Ваня выигрывает за один ход winning_one = [] for x in range(1, 88): if f1(x, 1) == 1: winning_one.append(x) # Исключаем позиции, где Ваня выигрывает за один ход result = [x for x in winning_two if x not in winning_one] print(min(result)) ``` Функция `f` анализирует игру на глубину 5 ходов (два хода Вани). Функция `f1` анализирует игру на глубину 3 ходов (один ход Вани). Ищем минимальное значение из позиций, где Ваня выигрывает за два хода, но не за один.

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