Ваня выигрывает первым или вторым ходом
Два игрока, Петя и Ваня, играют в игру. Перед ними две кучи камней, ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в одну из куч 1 камень или увеличить одну из куч в 2 раза. Игра заканчивается, когда суммарное количество камней в двух кучах становится не менее 171. Выигрывает игрок, сделавший последний ход, то есть первым получивший такую позицию. В начальный момент в первой куче 25 камней, во второй S камней, 1 ≤ S ≤ 145. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. Найдите наименьшее значение S, при котором одновременно выполняются два условия: у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым своим ходом при любой игре Пети; у Вани нет стратегии, которая позволяет ему гарантированно выиграть первым ходом.
Источник: ФИПИ (Основная 19.06.2026), № 31157
Показать разбор
- Напиши функцию f(a, b, m), где m это число оставшихся ходов обоих игроков. Игра кончена, если a + b >= 171: тогда верни m % 2 == 0, а при m == 0 верни 0.
- Запиши в список h четыре хода: +1 к каждой куче и умножение каждой кучи на 2.
- В конце пиши any(h) при нечётном m и all(h) при чётном. Первым ходит Петя, но считаем за Ваню, поэтому число m чётное.
- Перебери S и оставь те, где верно not f(25, s, 2) and f(25, s, 4). Условие not f(25, s, 2) обязательно: f(25, s, 4) включает и выигрыш первым ходом.
- Напечатай наименьшее значение из списка.
def f(a, b, m):
if a + b >= 171:
return m % 2 == 0
if m == 0:
return 0
h = [f(a + 1, b, m - 1), f(a, b + 1, m - 1), f(a * 2, b, m - 1), f(a, b * 2, m - 1)]
return any(h) if m % 2 != 0 else all(h)
r = [s for s in range(1, 146) if not f(25, s, 2) and f(25, s, 4)]
print(min(r))