19.02 Перекладывание камней две кучи
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один или три камня или увеличить количество камней в одной из куч на количество камней в другой куче. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 124. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в обеих кучах в сумме стало 124 или больше камней.
В начальный момент в первой куче было 13 камней, во второй куче – S камней; 1 
S 
110.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите значение S, при котором у Вани есть выигрышная стратегия, при которой он побеждает своим первым ходом.
Программное решение
from functools import lru_cache @lru_cache(None) def game(first_heap, second_heap,count_moves = 0): # Функция игры. # count_moves - это счётчик ходов в партии. # Он добавлен для ускорения выполнения программы за счёт того, что продолжительные партии будут обрываться. # Если в партии совершено слишком много ходов, то данная партия нам неинтересна и нам не важно кто в ней победит. if first_heap + second_heap >= 124: # Если сумма камней в кучах стала больше 123 return 0 # Прекращаем игру if count_moves > 6: # Если в партии совершено слишком много ходов return 10**5 # Прерываем игру, возвращая очень большое значение moves = [game(first_heap, second_heap+1,count_moves+1), game(first_heap+1, second_heap,count_moves+1), game(first_heap + 3, second_heap,count_moves+1),game(first_heap, second_heap + 3,count_moves+1), game(first_heap + second_heap, second_heap,count_moves+1),game(first_heap, second_heap + first_heap,count_moves+1),] # Генерация всех возможных ходов 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,111): # если в данной позиции возможен выигрыш Вани первым ходом if game(13,i) == -1: print(i)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) четыре камня, увеличить количество камней в одной из куч в два или три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 169. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в обеих кучах в сумме стало 169 или больше камней.
В начальный момент в первой куче было 15 камней, во второй куче – S камней; 1 
S 
152.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите минимальное значение S, при котором у Вани есть выигрышная стратегия, при которой он побеждает своим первым ходом.
Программное решение
from functools import lru_cache @lru_cache(None) def game(first_heap, second_heap,count_moves = 0): # Функция игры. # count_moves - это счётчик ходов в партии. # Он добавлен для ускорения выполнения программы за счёт того, что продолжительные партии будут обрываться. # Если в партии совершено слишком много ходов, то данная партия нам неинтересна и нам не важно кто в ней победит. if first_heap + second_heap >= 169: # Если сумма камней в кучах стала больше 168 return 0 # Прекращаем игру if count_moves > 6: # Если в партии совершено слишком много ходов return 10**5 # Прерываем игру, возвращая очень большое значение moves = [game(first_heap, second_heap+4,count_moves+1), game(first_heap+4, second_heap,count_moves+1), game(first_heap * 2, second_heap,count_moves+1),game(first_heap, second_heap * 2,count_moves+1), game(first_heap * 3, second_heap,count_moves+1),game(first_heap, second_heap * 3,count_moves+1),] # Генерация всех возможных ходов 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,153): # если в данной позиции возможен выигрыш Вани первым ходом if game(15,i) == -1: print(i) break
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую из куч количество камней в другой куче или удвоить количество камней в меньшей куче. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 205. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах будет 205 или больше камней.
В начальный момент в первой куче было 9 камней, во второй куче – S камней; 1 
S 
196. Будем говорить, что
игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите минимальное значение S, при котором у Пети есть выигрышная стратегия, при которой он побеждает своим первым ходом.
Программное решение
from functools import lru_cache @lru_cache(None) def game(first_heap, second_heap,count_moves = 0): # Функция игры. # count_moves - это счётчик ходов в партии. # Он добавлен для ускорения выполнения программы за счёт того, что продолжительные партии будут обрываться. # Если в партии совершено слишком много ходов, то данная партия нам неинтересна и нам не важно кто в ней победит. if first_heap + second_heap >= 205: # Если сумма камней в кучах стала больше 204 return 0 # Прекращаем игру if count_moves > 6: # Если в партии совершено слишком много ходов return 10**5 # Прерываем игру, возвращая очень большое значение moves = [] # Список всех возможных ходов if first_heap > second_heap: # если камней в первой куче больше чем во второй # то добавляем камни только во вторую кучу moves = [game(first_heap,second_heap+first_heap,count_moves+1),game(first_heap,second_heap*2,count_moves+1)] # Генерация ходов else: # иначе если во второй куче камней больше чем в первой или количество камней в кучах равно # то добавляем камни только в первую кучу moves = [game(first_heap+ second_heap, second_heap,count_moves+1 ), game(first_heap*2, second_heap,count_moves+1)] # Генерация ходов 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,197): # если в данной позиции возможен выигрыш Пети первым ходом if game(9,i) == 1: print(i) break
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч 7 камней, 11 камней или умножить количество камней в куче на 2. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 186. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах будет 186 или больше камней.
В начальный момент в первой куче было 10 камней, во второй куче – S камней; 1 
S 
175.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах
противника.
Найдите минимальное значение S, при котором у Пети есть выигрышная стратегия, при которой он побеждает своим первым ходом.
Программное решение
from functools import lru_cache @lru_cache(None) def game(first_heap, second_heap,count_moves = 0): # Функция игры. # count_moves - это счётчик ходов в партии. # Он добавлен для ускорения выполнения программы за счёт того, что продолжительные партии будут обрываться. # Если в партии совершено слишком много ходов, то данная партия нам неинтересна и нам не важно кто в ней победит. if first_heap + second_heap >= 186: # Если сумма камней в кучах стала больше 185 return 0 # Прекращаем игру if count_moves > 6: # Если в партии совершено слишком много ходов return 10**5 # Прерываем игру, возвращая очень большое значение moves = [game(first_heap, second_heap+7,count_moves+1), game(first_heap+7, second_heap,count_moves+1), game(first_heap + 11, second_heap,count_moves+1),game(first_heap, second_heap + 11,count_moves+1), game(first_heap * 2, second_heap,count_moves+1),game(first_heap, second_heap * 2,count_moves+1),] # Генерация всех возможных ходов 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,176): # если в данной позиции возможен выигрыш Пети первым ходом if game(10,i) == 1: print(i) break
