Задача к ЕГЭ по информатике на тему «Перекладывание камней две кучи» №2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $6$ камней, а в другой $7$ камней; такую позицию мы будем обозначать $(6,7).$ За один ход из позиции $(6,7)$ можно получить любую из четырёх позиций: $(8,7),(6,9),(18,7),(6,21).$ Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $63.$

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет $63$ или более камней. В начальный момент в первой куче было $7$ камней, во второй куче $S$ камней, $1 ≤ S ≤ 55.$

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

Найдите минимальное значение $S$ , при котором Ваня выигрывает своим первым ходом при любой игре Пети.

Решение руками Определим при каком наименьшем значении S Петя побеждает первым ходом:

= 63 − 7 » class=»math» src=»/images/inform/reshen/reshen-3285-1.svg» width=»auto»> = = 56 == S >= 19 » class=»math» src=»/images/inform/reshen/reshen-3285-2.svg» width=»auto»>

При $S ≥ 19$ Петя выигрывает своим первым ходом. Рассмотрим позицию $(18,7) :$

$(18,7) ⇒ (56,7) ⇒ (56,21) ⇒$ Ваня выиграл за $1$ ход
$(18,7) ⇒ (18,21) ⇒ (56,21) ⇒$ Ваня выиграл за $1$ ход
$(18,7) ⇒ (20,7) ⇒ (60,7) ⇒$ Ваня выиграл за $1$ ход
$(18,7) ⇒ (18,9) ⇒ (56,9) ⇒$ Ваня выиграл за $1$ ход

Значит это позиция выигрыша Вани первым ходом. Ответ $18$ .

Решение БУ

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 63:  # Если камней в кучах стало больше 62
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+2), game(first_heap+2, second_heap),
             game(first_heap * 3, second_heap),game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    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,56):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(7,i) == -1:
        print(i)
        break

Решение АР

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if sum(heap) >= 63:
        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, 56):
    if game((7, s)) == ’V1’:
        print(s)
        break

Ответ: 18