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