My Python3 code produces the correct result for the sample input, but
gives 'Wrong answer' for the 1st test set. Can anyone give me a hint of
how to fix it?
As for the algorithm, I use a priority queue to give priority to
percentages whose fractional part is as close as possible to 0.5 and
don't touch percentages whose fractional part is already >= 0.5.
from heapq import heappop, heappush
def main():
T = int(input()) # the number of test cases
for case in range(1, T+1):
total_people, num_languages = map(int, input().split())
freq = map(int, input().split())
percent_per_person = 100/total_people
low_scores = []
not_responded = total_people
res = 0
for f in freq:
p = f*percent_per_person
if 0 < p-int(p) < 0.5:
heappush(low_scores, (-(p-int(p)), p))
else:
res += round(p)
not_responded -= f
while not_responded:
try:
diff, p = heappop(low_scores)
except IndexError:
p = 0
p += percent_per_person
if 0 < p-int(p) < 0.5:
heappush(low_scores, (-(p-int(p)), p))
else:
res += round(p)
not_responded -= 1
res += sum(round(x[1]) for x in low_scores)
print('Case #{}: {}'.format(case, res))
main()
--
Regards,
Eugene
--
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/ddc1aeea-7f2c-563c-b716-bd2a03cb17a9%40gmail.com.
For more options, visit https://groups.google.com/d/optout.
