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

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

=

При Петя выигрывает своим первым ходом. Рассмотрим позицию

1. Ваня выиграл за ход
2. Ваня выиграл за ход
3. Ваня выиграл за ход
4. Ваня выиграл за ход

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

Решение БУ

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