Question

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

Найденные значения запишите в ответе в порядке возрастания.

Accepted Answer

39 40

Answer

Идея решения: использовать рекурсивный анализ игровых позиций с учётом чётности хода, чтобы выделить позиции, где первый игрок не выигрывает сразу, но гарантирует победу на втором ходу. Обозначим позицию как $(x, y, h)$, где $x$ и $y$ — текущие значения, $h$ — номер хода. Функция $f(x, y, h)$ возвращает 1, если текущий игрок может выиграть, и 0 иначе. Условие победы: $x + y \geq 154$ на ходу Пети (ход 4 или позже). На нечётных ходах (ходы Пети) игрок выигрывает, если существует хотя бы один ход, приводящий к победе. На чётных ходах (ходы Вани) Петя выигрывает, только если все возможные ходы Вани приводят к позициям, где Петя может выиграть. ```python def f(x, y, h): if h == 4 and x + y >= 154: return 1 elif h == 4 and x + y < 154: return 0 elif x + y >= 154 and h < 4: return 0 else: if h % 2 != 0: 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)) else: return (f(x + 4, y, h + 1) and f(x, y + 4, h + 1) and f(x * 3, y, h + 1) and f(x, y * 3, h + 1)) result = [] for x in range(1, 143): if f(x, 11, 1) == 1: result.append(x) print(result[:2]) ``` Перебираем все начальные значения $S$ от 1 до 142 (так как $S + 11 < 154$). Для каждого $S$ проверяем, выигрывает ли Петя при стартовой позиции $(S, 11, 1)$. Отбираем первые два значения, удовлетворяющие условиям задачи.

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