fork(1) download
copy 
  1. import math
  2. from decimal import Decimal
  3.  
  4. BIG_BUT_NOT_INFINITE = 1e30
  5. F = 100
  6. H = 80
  7.  
  8. def solve(F, H, pr_h=.5, eps=1e-6):
  9.   # X(f, h) := expected number of flips to win given we need h heads out of f
  10.   #            flips and optimal strategy
  11.   # X(f, h) := { 0             if h = 0
  12.   #            { X(F, H)       if f < h
  13.   #            { min(          otherwise
  14.   #                1 + X(f-1, h-1) * Pr(h) + X(f-1, h) * (1 - Pr(h)),
  15.   #                X(F, H)
  16.   #              )
  17.   #
  18.   # X(f, h) depends on X(F, H) so it can't be computed.
  19.   # So introduce X_est(F, H) as a guess for X(F, H).
  20.   # And introduce X_conv(f, h) which is X(f, h) but it uses X_est(F, H)
  21.   # instead of X(F, H) in the definition above.
  22.   #
  23.   # If X_est(F, H) <= X(F, H), then X_conv(F, H) = X_est(F, H).
  24.   # This is because it will just "restart" and return X_est(F, H) immediately.
  25.   # So we can find the largest value of X_est(F, H) for which X_conv(F, H) != X_est(F, H).
  26.   # That should be the correct value of X_est(F, H).
  27.  
  28.   pr_h_d = Decimal(pr_h)
  29.   eps_d = Decimal(eps)
  30.  
  31.   def x_conv(x_est):
  32.     cache = {}
  33.     def x(f, h):
  34.       if h == 0: return 0
  35.       if f < h: return x_est
  36.  
  37.       cache_key = (f, h)
  38.       if cache_key not in cache:
  39.         do_flip = 1 + x(f-1, h-1) * pr_h_d + x(f-1, h) * (1 - pr_h_d)
  40.         cache[cache_key] = min(do_flip, x_est)
  41.       return cache[cache_key]
  42.     return x
  43.  
  44.   lo = Decimal(H)
  45.   hi = Decimal(BIG_BUT_NOT_INFINITE)
  46.   while hi - lo > eps_d:
  47.     x_est_guess = (lo + hi) / Decimal(2)
  48.     x_conv_guess = x_conv(x_est_guess)(F, H)
  49.     if abs(x_conv_guess - x_est_guess) < eps_d:
  50.       lo = x_est_guess
  51.     else:
  52.       hi = x_est_guess
  53.  
  54.   return x_conv(lo)
  55.  
  56. oracle = solve(F, H)
  57.  
  58. # How many flips at the start of the game?
  59. print(oracle(F, H))
  60. print(oracle(2, 2))
  61. print(oracle(20, 20))
  62. print(oracle(40, 40))
  63.  
Success #stdin #stdout 0.63s 15720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11211755096.90825093646328600
8408816324.181188952347464365
11211744406.54537227084826462
11211755096.90825193646328582
https://ideone.com/EVur2C
language:
Python 3 (python  3.9.5)
created:
3 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!