Задача к ЕГЭ по информатике на тему «Теория игр» №11

В игре, описанной в задании 19, в начальный момент в первой куче было S камней, а во второй — 7 камней, 1 ≤ S ≤ 45 Укажите минимальное и максимальное из таких значений S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. Найденные значения запишите в порядке убывания без пробелов и разделителей.

Программная реализация

from functools import lru_cache
@lru_cache(None)
def f(a,b,c = 0):
    if a+b >= 61:
        return 0
    if c > 3:
        return 10000
    if a > b: t = [f(a+i,b,c+1) for i in range(1, a+1)]
    else: t = [f(a,b+i,c+1) for i in range(1, b+1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)
ans = []
for i in range(1,46):
    if f(7,i) == 2:
        ans += [i]
print(max(ans),min(ans))

Ответ: 2513
Оцените статью
Я решу все!