Question

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

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

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

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

Accepted Answer

3134

Answer

Идея решения: найти все позиции, из которых Петя не выигрывает за один ход, но гарантированно выигрывает за два хода, независимо от ответов Вани. Используем рекурсивную функцию, которая отслеживает номер хода и определяет, может ли текущий игрок достичь победы на нужном ходу. Функция `f(k1, k2, hod)` возвращает 1, если Петя может выиграть своим вторым ходом (ход номер 3), и 0 иначе: - Если сумма камней $\ge 77$ на ходе 3 (второй ход Пети) — Петя выиграл. - Если сумма камней $\ge 77$ раньше хода 3 — Петя не выиграл на нужном ходе. - На нечётных ходах (Петя) — проверяем, существует ли хотя бы один выигрышный ход (оператор `or`). - На чётных ходах (Ваня) — проверяем, что при всех его ходах Петя остаётся в выигрышной позиции (оператор `and`). ```python def f(k1, k2, hod): if hod == 3 and k1 + k2 >= 77: return 1 elif hod == 3 and k1 + k2 < 77: return 0 elif hod < 3 and k1 + k2 >= 77: return 0 else: if hod % 2 != 0: # ход Пети return (f(k1 + 1, k2, hod + 1) or f(k1, k2 + 1, hod + 1) or f(k1 * 2, k2, hod + 1) or f(k1, k2 * 2, hod + 1)) else: # ход Вани return (f(k1 + 1, k2, hod + 1) and f(k1, k2 + 1, hod + 1) and f(k1 * 2, k2, hod + 1) and f(k1, k2 * 2, hod + 1)) result = [] for s in range(1, 70): if f(7, s, 1) == 1 and not (f(7, s, 0) == 1): result.append(s) print(''.join(map(str, result))) ``` Проверим найденные значения: При $S = 31$: Петя удваивает первую кучу, получая (14, 31). После любого хода Вани возникает одна из позиций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех случаях Петя удваивает вторую кучу и достигает суммы $\ge 77$, выигрывая вторым ходом. При $S = 34$: Петя добавляет камень в первую кучу, получая (8, 34). После любого хода Вани возникает одна из позиций: (9, 34), (8, 35), (16, 34), (8, 68). Во всех случаях Петя удваивает вторую кучу и выигрывает вторым ходом.

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