Петя и Ваня по очереди ходят в игре с одной кучей. Начинает Петя. За ход можно прибавить 1, прибавить 2 или удвоить число камней. Игроку нельзя повторять команду, которую он выполнил на своём предыдущем ходу. Команду соперника и свои более ранние команды повторять можно.
Побеждает игрок, после хода которого в куче не меньше 29 камней. Изначально в куче камней, .
Найдите два значения , при которых Ваня гарантирует победу вторым ходом, но не может гарантировать её первым. Запишите значения по возрастанию.
Решение:
previous хранит номер последней команды текущего игрока, other — номер команды соперника. При переходе хода other становится previous, а выполненная команда сохраняется для следующей очереди игрока. Проверяем победу Вани не позднее четвёртого общего хода и исключаем гарантированную победу за два общих хода.
def F(k, x, previous=0, other=0):
if k >= 29:
return x % 2 == 0
if x == 0:
return 0
hod = []
if previous != 1:
hod.append(F(k + 1, x - 1, other, 1))
if previous != 2:
hod.append(F(k + 2, x - 1, other, 2))
if previous != 3:
hod.append(F(k * 2, x - 1, other, 3))
return any(hod) if x % 2 != 0 else all(hod)
values = [k for k in range(1, 29)
if not F(k, 2) and F(k, 4)]
print(*values)
Ответ — 10 11.