# Verificación del Corolario 12.12: máximo de las medias de ciclo del grafo A
# (grafo modular sin el nodo 8 impar y sin el circuito consecutivo 7,8,4i,4,2i,7).
import math
from collections import defaultdict
r=lambda v:(v-1)%9+1
nodes=[(d,p) for d in range(1,10) for p in (0,1)]          # p=1: impar
def succ(v):
    d,p=v
    return [(r(5*d),0),(r(5*d),1)] if p==0 else [(r(3*d+1),0)]
C11=[(7,0),(8,0),(4,1),(4,0),(2,1),(7,0)]
start=[(v,) for v in nodes if v!=(8,1)]
E=defaultdict(list); seen=set(start); st=list(start)
while st:
    h=st.pop()
    for u in succ(h[-1]):
        if u==(8,1): continue
        nh=(h+(u,))[-6:]
        if list(nh)==C11: continue
        nh=nh[-5:]
        E[h].append(nh)
        if nh not in seen: seen.add(nh); st.append(nh)
S=list(seen); idx={s:i for i,s in enumerate(S)}; n=len(S)
w=lambda s: math.log2(22/7) if s[-1][1]==1 else -1.0
NEG=-1e18; D=[[NEG]*n for _ in range(n+1)]
for i in range(n): D[0][i]=0
for k in range(1,n+1):
    for s in S:
        a=D[k-1][idx[s]]
        if a==NEG: continue
        for t in E[s]:
            j=idx[t]; D[k][j]=max(D[k][j],a+w(s))
mu=max(min((D[n][v]-D[k][v])/(n-k) for k in range(n) if D[k][v]!=NEG)
       for v in range(n) if D[n][v]!=NEG)
print('estados:',n)
print('media máxima:',mu,' valor teórico:',(3*math.log2(22/7)-5)/8)

# ---- Certificado exacto con pesos enteros ----
# La media de un ciclo con i pasos impares y p pares es rho*(w+1)-1, con rho=i/(i+p):
# el máximo de las medias corresponde al máximo de rho. Se certifica rho <= a/(a+b)
# comprobando, con aritmética entera, que no hay ciclos de peso positivo cuando los
# pasos impares pesan b y los pares -a (Bellman-Ford desde potenciales nulos).
def sin_ciclos_positivos(b, a):
    dist={s:0 for s in S}
    for it in range(n+1):
        cambio=False
        for s in S:
            ws = b if s[-1][1]==1 else -a
            for t in E[s]:
                if dist[s]+ws > dist[t]:
                    dist[t]=dist[s]+ws; cambio=True
        if not cambio: return True
    return False
print('certificado exacto: ningún ciclo con proporción de impares mayor que 3/8:', sin_ciclos_positivos(5,3))