Google Code Jam 2018 / 1A / Bit Party

bit_part.py

t = int(raw_input().strip())

M, S, P = range(3)


def show(case, sol):
    print "Case #%s: %s" % (case, sol)


def transform(m, s, p, limit):
    can = max(0, limit - p) / s
    return min(m, can)


def check(stuff, limit, r, b):
    stuff2 = []
    for m, s, p in stuff:
        stuff2.append(transform(m, s, p, limit))
    stuff2 = sorted(stuff2, reverse=True)
    return sum(stuff2[:r]) >= b


for case in xrange(1, t + 1):
    stuff = []
    r, b, c = map(int, raw_input().strip().split())
    for _ in xrange(c):
        mi, si, pi = map(int, raw_input().strip().split())
        stuff.append((mi, si, pi))

    low, high = 0, 1
    while not check(stuff, high, r, b):
        high *= 2

    while high - low > 1:
        mid = (low + high) / 2
        if check(stuff, mid, r, b):
            high = mid
        else:
            low = mid

    show(case, high)