# Решение задач типа 19-21 на 2 кучи программно
# по мотивам алгоритма Флойда-Уоршелла для поиска всех путей в Графе
# На примере Статграда 2 (декабрь 2022)
''' Правила игры
Два игрока, Пятачок и Винни, играют в следующую игру.
Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в меньшую кучу один камень, добавить два камня или увеличить количество камней в куче в два раза.
Изменять количество камней в большей куче не разрешается.
Определение победителя
Игра завершается, когда общее количество камней в двух кучах становится более 80.
Победителем считается игрок, сделавший последний ход, то есть
первым получивший 81 или больше камней в двух кучах.
'''
def okrug (p): # построение смежных вершин (КС) - все вершины допустимы для XY
W=[]
x,y=p[0],p[1]
if x<y :
W=[(x+1,y),(x+2,y),(x+x,y)]
elif x>y :
W=[(x,y+1),(x,y+2),(x,y+y)]
else :
W=[(x+1,y),(x+2,y),(x,y+1),(x,y+2)]
return W
XY=[] # двумерная матрица для возможных позиций
N=80 # параметр окончания игры вар1= 80 вар2 =60
st,M=12,68
for _ in range (2*N+1): # начальное заполнение таблицы XY
XY.append([None]*(2*N+1))
for i in range(1,2*N+1): # помечаем 0 (чет) выигрышные вершины
for j in range(1,2*N+1):
if i+j>N : XY[i][j]=0
for k in range(1,N+1): # игра не может продолжаться более N ходов
A=[] # список вершин, определившихся на ходе k
''' идея алгоритма состоит в том, чтобы на нечётных ходах определять
выигрышные вершины для Пяточка, а на чётных ходах выигрышные вершины
Винни.
Используем метод расскраски (двудольный граф) Если из вершины есть ход в
чётную вершину, то это НЕЧЁТНАЯ вершина. Если все ходы ведут в нечётные
вершины, то это ЧЁТНАЯ вершина
'''
for i in range(1,N+1): # переберам все вершины
for j in range(1,N+1):
if XY[i][j] != None : continue # вершина определена, пропускаем
W = okrug((i,j)) # получение смежных вершин (КС - компоненты смежности)
if k%2 == 1 : # определяем НЕЧЁТНЫЕ вершины (для Пяточка)
flag=False # изначально перехода в ЧЁТ нет
for v in W : # пробег по КС
r=XY[v[0]][v[1]] # значение вершины перехода
if r != None and r%2 == 0 : flag =True # есть "переход в ЧЁТ"
if flag : # фиксация результата
XY[i][j]=k # запись в таблицу положительного нечётного числа
A.append((i,j)) # добавление вершины в список обновления
else : # определяем ЧЁТНЫЕ вершины (для Винни)
flag=True # изначально ВСЕ переходы ведут в НЕЧЁТ
for v in W : # пробег по КС
r=XY[v[0]][v[1]] # значение вершины перехода
if r==None or r%2 == 0 : flag =False # есть исключение
if flag : # фиксация результата
XY[i][j]=-k # запись в таблицу отрицательного чётного числа
A.append((i,j)) # добавление вершины в список обновления
if A : print((k,len(A))) # отладочная печать
else : break # новых вершин НЕТ, прерываем построение
print ('======= Вывод результатов для опредение ответов ========')
''' В начальный момент в первой куче было 12 камней, а во второй – S камней, 1 ≤ S ≤ 68.
Для ответов на ВСЕ вопросы задания достаточно вывести строку с номером 12'''
st,M=12,68 # начальные значения/ограничения var1 12,68 var2 8,52
for j in range(1,M+1):
print((j,XY[st][j]),end=' ')
''' Задание 19 - Укажите минимальное из таких значений S, при которых Пятачок
не может выиграть за один ход, но при любом ходе Пятачка
Винни сможет выиграть своим первым ходом.
Для ответа НАДО ВЫВЕСТИ значения строки XY равные -2 '''
print('\n z19: ')
for j in range(1,M+1):
if XY[st][j]==-2 : print((j,XY[st][j]),end=' ')
''' Задание 20 - укажите минимальное и максимальное из таких значений S,
при которых Пятачок не может выиграть первым ходом, но у Пятачка есть
выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Винни.
Для ответа НАДО ВЫВЕСТИ значения строки XY равные 3 '''
print('\n z20: ',)
for j in range(1,M+1):
if XY[st][j]==3 : print((j,XY[st][j]),end=' ')
''' Задание 21 - найдите максимальное из таких значений S, при которых
у Винни есть выигрышная стратегия, позволяющая ему выиграть первым или вторым
ходом при любой игре Пятачка, но у Винни нет стратегии, которая позволяла
бы ему гарантированно выиграть первым ходом.
Для ответа НАДО ВЫВЕСТИ значения строки XY равные -4 '''
print('\n z21: ',end=' ')
for j in range(1,M+1):
if XY[st][j]==-4 : print((j,XY[st][j]),end=' ')