Для игры, описанной в задании с ID #56420, укажите два минимальных значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
В ответе значения запишите в порядке возрастания без пробелов и разделителей.
Решение
Исходя из прошлого задания, мы знаем, что областью проигрыша является промежуток от 76 до 91(по сумме количества камней в кучах). Область проигрыша – это такая область, в которой игрок, попавший в этот промежуток, гарантированно проигрывает в партии.
Значит, нас интересуют такие ситуации, когда Ваня попадает своим ходом в эту область и следующим ходом Петя гарантированно побеждает.
Минимальные значения камней во второй куче, при которых возможна такая ситуация: 44 и 45. Ответ:4445
Решение программой
from functools import lru_cache lru_cache(None) def f(a,b,c = 0):# Параметр ’с’ в этой программе - это счётчик,сделанных ходов в данной партии. # В данной задаче он обязателен,поскольку изначальное кол-во камней может быть слишком мало,а также есть ходы,которые не так сильно увеличивают кол-во камней в куче(+2,+5),как,например ход (+15). # По этой причине у нас может возникнуть ошибка,связанная с превышением глубины рекурсии или же программа будет слишком долго высчитывать значения. if a+b >= 91: return 0 if c > 7: return 1000 if a < b: t = [f(a+2,b,c+1),f(a+5,b,c+1),f(a+15,b,c+1)] else: t = [f(a,b+2,c+1),f(a,b+5,c+1),f(a,b+15,c+1)] n = [i for i in t if i <= 0] if n: return -max(n) + 1 return -max(t) for i in range(1,61): if f(15,i) == 2: print(i)