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

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

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

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

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

Если такого значения нет, в ответ запишите $0.$

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

Мы знаем, что при $S = 21$ Петя выигрывает своим вторым ходом. Рассмотрим позицию $(20,4)$ . Петя сходит из нее в следующие позиции:

(21,4) = > (21,5) = > (21,6) = > (42,6) » class=»math» src=»/images/inform/reshen/reshen-3290-3.svg» width=»auto»> Ваня победил $2$ ходом

(20,5) = > (21,5) = > (21,6) = > (42,6) » class=»math» src=»/images/inform/reshen/reshen-3290-5.svg» width=»auto»> Ваня победил $2$ ходом

(40,4) = > (80,4) » class=»math» src=»/images/inform/reshen/reshen-3290-7.svg» width=»auto»> Ваня победил $1$ ходом

(20,8) = > (40,8) » class=»math» src=»/images/inform/reshen/reshen-3290-9.svg» width=»auto»> Ваня победил $1$ ходом

Ответ: $20$

Решение БУ

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 48:  # Если камней в кучах стало больше 47
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
             game(first_heap * 2, second_heap),game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,44):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(4,i) == -2:
        print(i)

Решение АР

from functools import lru_cache


def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)


@lru_cache(None)
def game(heap):
    if sum(heap) >= 48:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 44):
    if game((4, s)) == ’V2’:
        print(s)

Ответ: 20