Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Google Code Jam -- Rounding Error -- Solution in Python
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment