Code Jam 18 / 1B / Rounding Error

sol.py

from heapq import heappop as pop, heappush as push
from math import floor, ceil


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

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


def get_value(ci, n):
    return round(100. * ci / float(n))


def frac_val(ci, n):
    base = 100. * ci / float(n)
    return base - floor(base)


for ct in xrange(1, t + 1):
    n, l = map(int, raw_input().strip().split())
    cis = map(int, raw_input().strip().split())
    left = n - sum(cis)
    if 100 % n == 0:
        cis.append(left)
        sol = int(sum(map(lambda ci: get_value(ci, n), cis)))
        show(ct, sol)
        continue

    eps = 100.0 / n - floor(100. / n)
    cis.extend([0] * left)
    dis = []
    for ci in cis:
        if frac_val(ci, n) >= 0.5:
            dis.append((n + 1, ci))
        else:
            val = int(ceil((0.5 - frac_val(ci, n)) / eps))
            dis.append((val, ci))
    dis = sorted(dis, key=lambda x: x[0])
    eis = []
    for val, di in dis:
        if left >= val:
            eis.append(di + val)
            left -= val
        else:
            eis.append(di)
    eis.append(left)
    sol = int(sum(map(lambda ei: get_value(ei, n), eis)))
    show(ct, sol)