Петя неудачно, Ваня выигрывает первым ходом
Два игрока, Петя и Ваня, играют в игру. Перед ними две кучи камней, ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в одну из куч 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.
- Ход Пети неудачный, поэтому в конце пиши return any(h) для обоих игроков.
- Перебери S, первая куча равна 25, и оставь те S, где f(25, s, 2) истинно.
- Напечатай наименьшее значение из списка.
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)
r = [s for s in range(1, 146) if f(25, s, 2)]
print(min(r))