Петя выигрывает вторым ходом
Два игрока, Петя и Ваня, играют в игру. Перед ними две кучи камней, ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из одной из куч 2 камня или уменьшить одну из куч в 3 раза (результат деления округляется вниз). Игра заканчивается, когда суммарное количество камней в двух кучах становится не более 47. Выигрывает игрок, сделавший последний ход, то есть первым получивший такую позицию. В начальный момент в первой куче 16 камней, во второй S камней, S ≥ 32. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. Найдите наименьшее и наибольшее значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один ход; Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. В ответе запишите два числа через пробел по возрастанию.
Источник: ФИПИ (Пересдача 08.07.2026), № 31365
Показать разбор
- Напиши функцию f(a, b, m), где m это число оставшихся ходов обоих игроков. Игра кончена, если a + b <= 47: тогда верни m % 2 == 0, а при m == 0 верни 0.
- Запиши в список h четыре хода: минус 2 от каждой кучи и деление каждой кучи на 3 через //.
- В конце пиши any(h) при нечётном m, это ход Пети, и all(h) при чётном, это ход Вани.
- Перебери S и оставь те, где верно not f(16, s, 1) and f(16, s, 3): за один ход Петя не выигрывает, а за три хода обоих игроков выигрывает. Диапазон S возьми с запасом, сверху он не ограничен.
- Условие просит наименьшее и наибольшее, поэтому напечатай первый и последний элементы списка.
def f(a, b, m):
if a + b <= 47:
return m % 2 == 0
if m == 0:
return 0
h = [f(a - 2, b, m - 1), f(a, b - 2, m - 1), f(a // 3, b, m - 1), f(a, b // 3, m - 1)]
return any(h) if m % 2 != 0 else all(h)
r = [s for s in range(32, 1500) if not f(16, s, 1) and f(16, s, 3)]
print(r[0], r[-1])