Петя и Ваня по очереди ходят в игре с одной кучей. Начинает Петя. За ход можно прибавить 1, прибавить 2 или удвоить число камней. Игроку нельзя повторять команду, которую он выполнил на своём предыдущем ходу. Команду соперника и свои более ранние команды повторять можно.
Побеждает игрок, после хода которого в куче не меньше 29 камней. Изначально в куче камней, .
Найдите наибольшее , при котором Петя гарантирует победу третьим ходом, но не может гарантировать её первым или вторым ходом.
Решение:
previous хранит номер последней команды текущего игрока, other — номер команды соперника. При переходе хода other становится previous, а выполненная команда сохраняется для следующей очереди игрока. Третий ход Пети — пятый ход партии. F(k, 3) учитывает победу и первым, и вторым ходом Пети, поэтому одного исключения not F(k, 3) достаточно.
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, 3) and F(k, 5)]
print(values[-1])
Ответ — 9.