Question

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинания.

Accepted Answer

93102

Answer

Идея решения: найти начальные позиции, при которых второй игрок (Ваня) гарантирует победу за два своих хода, но не может выиграть за один ход. Построим две функции анализа игры: - `f(x, h)` — проверяет, может ли текущий игрок выиграть за два хода Вани (глубина поиска до 5 ходов); - `f1(x, h)` — проверяет, может ли текущий игрок выиграть за один ход Вани (глубина поиска до 3 ходов). Позиция считается выигрышной, если количество камней достигает 525 или более. На чётных ходах (ход Вани) ищем выигрышный ход через дизъюнкцию (достаточно одного хода). На нечётных ходах (ход Пети) проверяем все возможные ходы через конъюнкцию (Ваня должен выиграть при любом ходе Пети). ```python def f(x, h): if (h == 3 or h == 5) and x >= 525: return 1 elif h == 5 and x < 525: return 0 elif x >= 525 and h < 5: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) or f(x + 10, h + 1) or f(x * 5, h + 1)) else: return (f(x + 1, h + 1) and f(x + 10, h + 1) and f(x * 5, h + 1)) def f1(x, h): if h == 3 and x >= 525: return 1 elif h == 3 and x < 525: return 0 elif x >= 525 and h < 3: return 0 else: if h % 2 == 0: return (f1(x + 1, h + 1) or f1(x + 10, h + 1) or f1(x * 5, h + 1)) else: return (f1(x + 1, h + 1) and f1(x + 10, h + 1) and f1(x * 5, h + 1)) # Позиции, где Ваня выигрывает за два хода two_move_wins = [] for x in range(1, 525): if f(x, 1) == 1: two_move_wins.append(x) # Позиции, где Ваня выигрывает за один ход one_move_wins = set() for x in range(1, 525): if f1(x, 1) == 1: one_move_wins.add(x) # Ищем позиции, где есть победа за два хода, но нет за один result = [x for x in two_move_wins if x not in one_move_wins] print(result[:2]) ``` Анализ для $S = 93$: Петя может перейти в позиции 94, 103 или 465. При 465 Ваня сразу умножает на 5 и выигрывает. При 94 и 103 Ваня переводит в 104, откуда Петя может получить 105, 114 или 520. Во всех случаях Ваня умножает на 5 и выигрывает на втором ходу. Анализ для $S = 102$: Петя может перейти в позиции 103, 112 или 510. При 112 и 510 Ваня сразу умножает на 5 и выигрывает. При 103 Ваня переводит в 104, откуда Петя может получить 105, 114 или 520. Во всех случаях Ваня умножает на 5 и выигрывает на втором ходу.

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