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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из $15$ камней, за один ход можно получить кучу из $17$ или $30$ камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее $25$ . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет $25$ или больше камней. В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 24$ .

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

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

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗2$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $25 --= 12,5 2$ (округляем в большую сторону) = $13$

Получается, что в отрезке [13;24] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

Возьмем $S = 11$ . Тогда Петя может добавить 2 камня и станет 13 камней, либо увеличить кол-во камней в куче в 2 раза и станет 22 камня. И из 13, и из 22 Ваня выигрывает умножением на 2.

Возьмем $S = 12$ . Тогда Петя может добавить 2 камня и станет 14 камней, либо увеличить кол-во камней в куче в 2 раза и станет 24 камня. И из 14, и из 24 Ваня выигрывает умножением на 2.

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 25: # если камней в куче стало больше 24
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_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,25):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*2)
@lru_cache(None)
def game(h):
    if h >= 25:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
for s in range(1, 25):
    if game(s) == ’LOSE1’:
        print(s)

Ответ: 11