Для игры, описанной в задании 19, укажите максимальное значений S, при котором Ваня не может победить ни первым, ни вторым ходом, но Ваня побеждает своим третьим ходом при любой игре Пети.
Программное решение
from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap,last_move = ""): # Функция игры.
# last_move - это переменная для хранения данных о том, в какую кучу какой ход был последний ход.
# Например, 1_+5 - это ход +5 в 1-ую кучу.
if first_heap + second_heap >= 201: # Если сумма камней в кучах стала больше 200
return 0 # Прекращаем игру
moves = [] # Список возможных ходов в партии
if last_move == "": # Если это первый ход в партии (то есть нет предыдущего хода)
# тогда мы можем использовать любой ход
moves = [game(first_heap+5,second_heap,"1_+5"),game(first_heap,second_heap+5,"2_+5"),
game(first_heap+7,second_heap,"1_+7"),game(first_heap,second_heap+7,"2_+7"),
game(first_heap+2,second_heap,"1_+2"),game(first_heap,second_heap+2,"2_+2"),
game(first_heap*3,second_heap,"1_*3"),game(first_heap,second_heap*3,"2_*3")] # Генерация всех возможных ходов
elif last_move == "1_+5": # если последний ход это +5 в 1-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "2_+5": # если последний ход это +5 в 2-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "1_+7": # если последний ход это +7 в 1-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "2_+7": # если последний ход это +7 в 2-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "1_+2": # если последний ход это +2 в 1-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "2_+2": # если последний ход это +2 в 2-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"),
game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "1_*3": # если последний ход это *3 в 1-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap, second_heap * 3, "2_*3")]
elif last_move == "2_*3": # если последний ход это *3 в 2-ую кучу
# тогда мы можем использовать любой ход, кроме этого
moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
game(first_heap * 3, second_heap, "1_*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,151):
# если в данной позиции возможен выигрыш Вани третьим ходом
if game(16,i) == 3:
print(i)
Ответ: 57