Петя и Ваня по очереди меняют число камней в одной куче. Первым ходит Петя. За ход можно убрать 3 или 5 камней либо разделить размер кучи на 2 с округлением вверх. Например, из 21 камня можно получить 18, 16 или 11.
Партия заканчивается, когда остаётся не больше 23 камней. Выигрывает сделавший последний ход. Изначально в куче камней, .
Найдите максимальное , при котором Петя не может выиграть за один ход, а Ваня может выиграть своим первым ходом после любого хода Пети.
Решение:
Деление пополам с округлением вверх записываем как ceil(k / 2). При S > 368 даже после четырёх делений останется больше 23 камней. Проверяем F(k, 2): после любого хода Пети у Вани должен быть выигрышный ответ.
from math import ceil
def F(k, x):
if k <= 23:
return x % 2 == 0
if x == 0:
return 0
hod = [F(k - 3, x - 1), F(k - 5, x - 1),
F(ceil(k / 2), x - 1)]
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(24, 369)
if F(k, 2)]
print(values[-1])
Ответ — 49.
Ответ:
49