Петя и Ваня по очереди меняют число камней в одной куче. Первым ходит Петя. За ход можно убрать 3 или 5 камней либо разделить размер кучи на 2 с округлением вверх. Например, из 21 камня можно получить 18, 16 или 11.
Партия заканчивается, когда остаётся не больше 23 камней. Выигрывает сделавший последний ход. Изначально в куче камней, .
Найдите максимальное , при котором Ваня гарантирует победу первым или вторым ходом, но не может гарантировать победу первым ходом.
Решение:
Деление пополам с округлением вверх записываем как ceil(k / 2). При S > 368 даже после четырёх делений останется больше 23 камней. Проверяем победу Вани не позднее четвёртого общего хода и исключаем гарантированную победу за два общих хода.
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 not F(k, 2) and F(k, 4)]
print(values[-1])
Ответ — 101.
Ответ:
101