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

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

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

– Петя не может выиграть за один ход;

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

Найденные значения запишите в ответе в порядке возрастания через пробел.

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

Из предыдущего задания мы знаем, что в значении $38$ , $39$ Ваня гарантированно выигрывает своим первым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведет в $38$ или $39$ – это значение, в котором Петя выигрывает вторым ходом. Распишем значение и стратегии, при которых Петя побеждает своим вторым ходом:

$S = 19$ . Петя может увеличить количество камней до $38$ ходом $∗2$ .

$S = 35$ Петя может увеличить количество камней до $38$ ходом $+ 3$ .

$S = 36$ Петя может увеличить количество камней до $39$ ходом $+ 3$ или до $38$ ходом $+ 2$ .

$S = 37$ Петя может увеличить количество камней до $39$ ходом $+ 2$ .

В ответ нужно указать два наименьших значения S. Ответ: $19$ $35$

Решение БУ

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)

Ответ: 19 35