Петя неудачно, Ваня выигрывает первым ходом
Два игрока, Петя и Ваня, играют в игру. Перед ними две кучи камней, ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из одной из куч 3 камня или уменьшить одну из куч в 3 раза (результат деления округляется вниз). Игра заканчивается, когда суммарное количество камней в двух кучах становится не более 53. Выигрывает игрок, сделавший последний ход, то есть первым получивший такую позицию. В начальный момент в первой куче 19 камней, во второй S камней, S ≥ 35. Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети (Петя ходом не закончил игру). Укажите минимальное значение S, при котором такая ситуация возможна.
Источник: ФИПИ (Резервная 22.06.2026), № 31227
Показать разбор
- Напиши функцию f(a, b, m), где m это число оставшихся ходов обоих игроков. Игра кончена, если a + b <= 53: тогда верни m % 2 == 0, а при m == 0 верни 0.
- Запиши в список h четыре хода: минус 3 от каждой кучи и деление каждой кучи на 3 через //.
- Ход Пети неудачный, поэтому в конце пиши return any(h) для обоих игроков.
- Перебери S, первая куча равна 19, и оставь те S, где f(19, s, 2) истинно. Сверху S не ограничена, поэтому возьми диапазон с запасом.
- Напечатай наименьшее значение из списка.
def f(a, b, m):
if a + b <= 53:
return m % 2 == 0
if m == 0:
return 0
h = [f(a - 3, b, m - 1), f(a, b - 3, m - 1), f(a // 3, b, m - 1), f(a, b // 3, m - 1)]
return any(h)
r = [s for s in range(35, 400) if f(19, s, 2)]
print(min(r))