# This is the Python code which followed the rationale of the Test Set 3
analysis (N log N). Spent entirety of contest unsuccessfully debugging by
looking for test cases which it fails, but getting Wrong Answer each time.
import bisect
def solve():
N, L = map(int, input().split())
C = list(map(int, input().split())) # of length L
remaining = N - sum(C)
if 100 % N == 0:
return 100
# print("Beginning langs chosen:", C)
# 1) Generate the targets which round up
targets = [i for i in range(1, N) if round(100*i/N) >= 100*i/N]
targets += [N]
least = targets[0] if len(targets) > 0 else N
# print("Targets:", targets)
# 2) Find distance for each language from nearest target
diffs = [None for _ in range(L)] # diffs from each language to next target
for i in range(L):
ind = bisect.bisect_left(targets, C[i])
diffs[i] = (targets[ind] - C[i], i)
# alternatively, use a heap (diffs, lang_ind)
diffs.sort()
# print("Diffs:", diffs)
# 3) Allocate the persons, generating as many round ups as possible
for i in range(L):
margin, ind = diffs[i]
if margin >= least or remaining < margin: # we can just form new
language groups now
break
C[ind] += margin
remaining -= margin
# 4) Calculate
total = sum(round(100*C[i]/N) for i in range(L))
# deal with the remaining
total += (remaining//least)*round(100*least/N)
remaining = remaining % least
total += round(100*remaining/N)
# print("Final langs chosen:", C)
return total
T = int(input())
for t in range(T):
ans = solve()
print("Case #{}: {}".format(t+1, ans))
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/25768800-d3a3-48cf-b7dd-4aa93c39b61c%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
