ПИШЕМ ПОДПРОГРАММЫ start (n) и next(p,n)
Разберем на примере
задания 49932
Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в большую из куч пять камней или увеличить количество камней
в меньшей куче в два раза. Если количество камней в кучах одниковое, то в любую из куч можно добавить три камня.
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда произведение камней в кучах становится не менее N.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию,
при которой произведение камней в кучах будет N или более.
В начальный момент в первой куче было x камней, во второй куче – y камней;
1 ≤ x*y <N.
Возможно несколько подходов к хранению вершин графа с помощью словаря и списка/множества стартовых вершин.
Вариант 1: В словарь
D записываются все возможные "финальные" вершины с раскраской,
На каждом шаге обработки в словарь добавляются новые вершины с раскраской (цвет определяется чётностью номера такта/
"Стартовые" вершины помещаются в список/множество
Q.
На каждом шаге обработки проверяются все вершины из
Q. Вершины, получившие раскраску, помещаются в словарь,
остальные остаются в
Q для обработки на следующем шаге.
Вариант 1
def start(N): # подпрограмма начальной раскраски с параметром
D=dict() # создание словаря
Q=list() # создание списка
for x in range(1,2*N): # вариант без оптимизации
for y in range(1,2*N): # при оптимизации можно считать, что x ≤ y
if x*y<N : # проверка условия "финальная/стартовая"
Q.append((x,y)) # "стартовая" - в список
else: # "финальная" - в словарь
D[(x,y)]=0
return Q , D # возврат список, словарь
При таком варианте решения расходуется больше памяти,
но упрощается структура подпрограммы next(p,N) - не надо учитывать правила "завершения игры"
def next(p,N): # подпрограмма получения смежных вершин
# N передаем (для стандартизации, но не используем)
x,y=p # распаковка вершины
if x==y: # 1 случай - кол-во камней в кучах одинаковое
return [(x,y+3), (x+3,y)]
if x<y : # 2 случай - в первой куче камней меньше
return [(2*x,y),(x,y+5)]
return [(x+5,y),(x,2*y)] # 3 случай - в первой куче камней больше
Вариант 2: "
Финальные" вершины в словарь
D не записываются.
Создается словарь вида {'W' : 0, 'L' : -1}.
Подпрограмма next(p,N) должна возвращать:
- 'W' для "
выигрышных финальных" вершин,
- 'L' для "
проигрышных финальных" вершин,
- номер вершины для "
стартовых" вершин
"Стартовые" вершины помещаются в список/множество
Q.
На каждом шаге обработки проверяются все вершины из
Q. Вершины, получившие раскраску, помещаются в словарь,
остальные остаются в
Q для обработки на следующем шаге.
Вариант 2.
def start(N): # подпрограмма начальной раскраски с параметром
D={'W' : 0, 'L': -1} # создание словаря
Q=list() # создание списка
for x in range(1,2*N): # заполнение списка с "оптимизацией"
for y in range(x,2*N): # считаем, что y не меньше x
if x*y<N : # "стартовая" - в список
Q.append((x,y))
return Q,D # возврат список, словарь
При таком варианте решения расходуется меньше памяти,
но усложняется структура подпрограммы next(p,N) -
надо учитывать правила "завершения игры"
def next(p,N): # подпрограмма получения смежных вершин
x,y=min(p),max(p) # распаковка и сортировка
A=set() # множество смежных вершин (множество - могут совпадать)
if x==y : # 1 случай - кол-во камней в кучах одинаковое
if x*(y+3) <N : # проверка на завершение игры
A.add((x,y+3)) # переход в "игровую" вершину
else : # переход в "финальную" вершину
A.add('W')
else: # 2 случай - в кучах разное кол-во камней
if 2*x*y < N : # проверка на завершение игры (для 1-команды)
A.add((min(2*x,y),max(2*x,y))) # переход в "игровую" вершину
else : # переход в "финальную" вершину
A.add('W')
if x*(y+5) < N : # проверка на завершение игры (для 2-команды)
A.add((x,y+5)) # переход в "игровую" вершину
else : # переход в "финальную" вершину
A.add('W')
return A # возврат множества переходов
Возможны и другие варианты хранения вершин графа.
Например, в Q можно записывать только "начальные стартовые" вершины,
а новые (полученные в
next(...)) добавлять в процессе решения.
Такой вариант потребует модификации подпрограмм
first и
second