Для игры, описанной в предыдущем задании, найдите минимальное и максимальное значения 
при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.
Решение руками
Для начала давайте найдём все позиции, где Петя побеждает первым ходом. Это все 
Теперь найдём все позиции, где Ваня побеждает первым ходом. Для этого при любом ходе нужно попасть в одну из позиций, где Петя побеждает первым ходом. Это позиции 
Рассмотрим минимальную нерасмотренную позицию 
Уменьшение на 
приведёт Петю в 
откуда он победит после любого хода Вани. Для максимального значения найдем наибольшее значение 
, с помощью которого можно попасть в позицию 
Для этого можно умножит 
Уменьшение значения 
в 
раза приведёт Петю в 
откуда он победит. В итоге минимальное и максимальное значения 
это числа 
и 
соответственно.
Решение программой
from functools import lru_cache
@lru_cache(None)
def game(heap): # Функция игры
if heap <= 2: # Если куча меньше или равна 2
return 0 # Возвращаем стартовое значение 0
# Список для возможных ходов,
# которые нужно добавить в зависимости от условий
steps = []
# 1 Условие
if heap % 2 == 0:
steps += [game(heap // 2)] # Убираем половину
else:
steps += [game(heap - 2)] # Убираем 2 камня
# 2 Условие
if heap % 3 == 0:
steps += [game(heap // 3)] # Убрать две трети равносильно оставить одну треть
else:
steps += [game(heap - 3)] # Убираем 3 камня
petya_win = [x for x in steps if x <= 0] # Выигрышные позиции для пети
if petya_win: # Если такие значения есть
return -max(petya_win) + 1
return -max(steps)
for s in range(3, 100):
if game(s) == 2: # Если Петя смог победить гарантированно за 2 хода
print(s)