Google Code Jam 18 / 1C / Lollipop shop

lollipop.py

from random import choice
import sys

t = int(raw_input().strip())
LOW, HIGH = 0.005, 0.1

def calc(p, count, curr, left):
    return pow(p, count) * pow(1.0 - p, curr - count) * pow(1.0 - p, left)

for case in xrange(1, t + 1):
    # sys.stderr.write("%s\n" % case)
    # sys.stderr.flush()
    n = int(raw_input().strip())
    counts = [0] * n
    has = [True] * n
    for i in xrange(1, n + 1):
        curr = map(int, raw_input().strip().split())[1:]
        if curr == []:
            print -1
            sys.stdout.flush()
            continue
        for el in curr:
            counts[el] += 1
        probs = [min(max(counts[j] / float(i), LOW), HIGH) for j in xrange(n)]
        # sys.stderr.write("probs: %s\n" % probs)
        # sys.stderr.flush()
        left = n + 1 - (i + 1)
        stuff = []
        for el in curr:
            stuff.append((calc(probs[el], counts[el], i, left), el))
        stuff = sorted(stuff, reverse=True)
        # sys.stderr.write("stuff: %s\n" % stuff)
        # sys.stderr.flush()
        found = None
        for _, el in stuff:
            if has[el]:
                found = el
                has[el] = False
                break
        if found is not None:
            print found
        else:
            print -1
        sys.stdout.flush()