Google Code Jam -- Rounding Error -- Solution in Python

codejam_2018_r1b_a.py

# usage:  (python3 a.py < a.in) > a.out
import time, sys, inspect, platform

print = lambda *a, **k: __builtins__.print(str(inspect.currentframe().f_back.f_lineno)+':',
    *a, file=sys.stderr, **k) if platform.node() in ['surfux', 'ssd'] else ...

#---------------------------------------------

'''
i know this is 'sort-by-goodness'
    so just add to the one closest to .5 ?
    i.e.  .4 > .3 > .2 > .1 > .0 > .9 > .8 > .7 > .6 > .5

round() in Python is broken
    >>> round(1.5)
    2
    >>> round(2.5)  # ?????
    2
    >>> round(3.5)
    4
    -> rounds to EVEN
    -> use custom round instead
'''

import heapq

round = lambda x: int(x + .5)

def run(data):
    n, data = data
    left = n - sum(data)
    data = data + [0] * left

    # .499 gets mapped to -.999 (first) and .501 to -.001 (last)
    fractional_key = lambda x: (.5 + x/n * 100) % 1

    # heap is a great data structure for inserting keys and getting the min
    data = [(-fractional_key(d), d) for d in data]
    heapq.heapify(data)

    for _ in range(left):
        # add 1 to the numerator (number of people) and put back into heap
        __, num_ppl = heapq.heappop(data)
        updated = (-fractional_key(num_ppl+1), num_ppl+1)
        heapq.heappush(data, updated)

    return sum([round(num_ppl/n * 100) for _, num_ppl in data])

#---------------------------------------------

def read_case():
    n, _ = [int(k) for k in list(input().split())]
    return (n, [int(k) for k in list(input().split())])

for i in range(int(input())):
    outstr = 'Case #'+str(i+1)+': '+str(run(read_case()))
    print(outstr, ' @ t =', time.clock())
    __builtins__.print(outstr)