Петя и Ваня по очереди меняют число камней в одной куче. Первым ходит Петя. За ход можно убрать 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, 1) and F(k, 3)]
print(values[0], values[-1])
Ответ — 50 98.
Ответ: