Ваня выигрывает первым или вторым ходом
Два игрока, Петя и Ваня, играют в игру. Перед ними две кучи камней, ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из одной из куч 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) при чётном. Первым ходит Петя, но считаем за Ваню, поэтому число m чётное.
- Перебери S и оставь те, где верно not f(16, s, 2) and f(16, s, 4). Условие not f(16, s, 2) обязательно: f(16, s, 4) включает и выигрыш первым ходом. Диапазон 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, 2) and f(16, s, 4)]
print(min(r))