Solution: Google Royale (Google Code Jam 2011 World Finals Problem E)

E.py

"""
""   Solution: Google Royale (Google Code Jam 2011 World Finals Problem E)
""   by: [email protected]
""   run: python E.py infile outfile
"""

import sys

# files
fin = file(sys.argv[1])
fout = open(sys.argv[2], 'w')
lines = fin.readlines()
tests = int(lines[0])

# parse input
games = {}
for i in range(1, tests+1):
    keys = ['A','M','V']
    vals = str(lines[i]).split(' ')
    vals[2] = (vals[2].splitlines())[0] # chomp trailing newline
    games[i] = dict(zip(keys, vals))

# solver
def rounds(A, M2, V):    
    # bets
    b0 = 0
    b1 = 1

    # inflection points
    f = True
    j = 2
    b2 = 1
    while f:
        k = 1 << j
        if (k > M2):
            break 
        a = min(V / 2, M2 / k)
        t = (k - 2) * a
        if (t >= b0):
            b0 = t
            b2 = j
            b1 = a
        j = j + 1
    
    # initial bet and win probability
    if (A >= b1):
        wp = float(A + b0) / float(V + b0)
        ib = min(min(A - b1, V - A), M2 / 2)
        t = A + b0
        j = 1
        f = True
        while f:
            k = 1 << j
            if (k - 1 > t):
                break 
            if (t % (k - 1) == 0):
                t0 = t / (k - 1)
                if (t0 <= A and A + t0 <= V and A + t0 + b0 <= M2):
                    ib = max(ib, t0)
            j = j + 1
    
        return (wp, ib)
    (wp, ib) = rounds(A, M2, b1)
    wp = wp * float(b1 + b0) / float(V + b0)
    return (wp, ib)

# betting rounds    
for i in range (1, tests+1):
    # game conditions
    A = int(games[i]['A'])
    M = int(games[i]['M'])
    V = int(games[i]['V'])
    M2 = 2 * M

    (wp, ib) = rounds(A, M2, V)

    # output file
    fout.write("Case #%d: %.12f %d\n" % (i, wp, ib))

"""
 
 Answer cribbed from contest victor rng..58 sol'n and contest analysis,
 There is nothing quite like a hard probability problem, now off to 
  break the bank at monte carlo ;)

"""