19.01 Перекладывание камней одна куча

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

Чтобы найти минимальное значение, при котором Петя выигрывает за один ход, нужно, чтобы Петя за один ход сделал кучу как можно больше, то есть увеличил количество камней в куче в раза. Поскольку победителем считается игрок, первым получивший позицию, в которой в куче будет минимум камней, а мы знаем, что Петя увеличит количество камней в куче в раза, то чтобы найти минимальное значение, при котором Петя выиграет за один ход, нужно разделить на . Получаем ответ: .

Действительно, возьмем , тогда Петя увеличит количество камней в куче в раза и получит камней, то есть выиграет.

Решение БУ

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

Решение АР

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