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

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

Для игры, описанной в предыдущем задании, найдите максимальное и минимальное значения $S$ , при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

Решение 1

Возможные значения $S : 82,81,61,43,42$ . В каждом из этих случаев Петя не может выиграть первым ходом. При $S = 82$ Петя может получить позицию $(20,41)$ , при $S = 42$ — позицию $(20,21)$ .

В первом случае после хода Вани возникнет одна из позиций $(19,41)$ , $(20,40)$ , $(10,41)$ , $(20,21)$ , во втором случае — одна из позиций $(19,21)$ , $(20,20)$ , $(10,21)$ , $(20,11)$ . В любой из перечисленных позиций Петя может выиграть, уменьшив вдвое количество камней в большей куче.

Решение 2

from functools import lru_cache
def moves(h):
    a, b = h
    m = []
    if a > 1:
        m += [((a + 1)//2, b), (a - 1, b)]
    if b > 1:
        m += [(a, (b + 1)//2), (a, b - 1)]
    return m

@lru_cache(None)
def f(h):
    if sum(h) <= 40:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
    if any(f(x) == ’V1’ for x in moves(h)):
        return ’P2’

for i in range(19, 100):
    h = i, 20
    if f(h) == ’P2’:
        print(i)

Ответ: 4282