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

Просмотров 6 Комментарии 0

Для игры, описанной в задании 10, найдите максимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение руками

Из предыдущих заданий мы знаем, что в значениях $19$ , $35$ , $36$ , $37$ Петя гарантированно побеждает своим вторым ходом и в отрезке значений [40;79] Петя побеждает гарантированно своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает вторым ходом или первым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает вторым или первым ходом:

$S = 33$ . Петя может увеличить количество камней до $35$ , $36$ или $66$ камней. В первых двух случаях, Ваня выиграет вторым ходом. В оставшемся случае, Ваня победит первым ходом.

$S = 34$ . Петя может увеличить количество камней до $36$ , $37$ или $68$ камней. В первых двух случаях, Ваня выиграет вторым ходом. В оставшемся случае, Ваня победит первым ходом.

В ответ нужно указать максимальное значение S. Ответ: $34$

Решение БУ

from functools import lru_cache


@lru_cache(None)
def f(x):
    if x >= 80:
        return 0
    t = [f(x + 2), f(x + 3), f(x * 2)]
    h = [i for i in t if i <= 0]
    if h:
        return -max(h) + 1
    else:
        return -max(t)


for s in range(1, 79 + 1):
    if f(s) == -2:
        print(s)

Ответ: 34