fork download
copy 
  1. from heapq import heappop, heappush
  2.  
  3. def get_p(f, total):
  4.     a = f * 100 // total
  5.     b = f * 100 % total
  6.     if 2 * b >= total:
  7.         a += 1
  8.     return a
  9.  
  10. def main():
  11.     T = int(input())  # the number of test cases
  12.  
  13.     for case in range(1, T+1):
  14.         total_people, num_languages = map(int, input().split())
  15.         freq = map(int, input().split())
  16.  
  17.         low_scores = []
  18.         not_responded = total_people
  19.         res = 0
  20.  
  21.         for f in freq:
  22.             key = f * 100 % total_people * 2
  23.             if 0 < key < total_people:
  24.                 heappush(low_scores, (-key, f))
  25.             else:
  26.                 res += get_p(f, total_people)
  27.             not_responded -= f
  28.  
  29.         while not_responded:
  30.             try:
  31.                 diff, f = heappop(low_scores)
  32.             except IndexError:
  33.                 f = 0
  34.  
  35.             f += 1
  36.             key = f * 100 % total_people * 2
  37.  
  38.             if 0 < key < total_people:
  39.                 heappush(low_scores, (-key, f))
  40.             else:
  41.                 res += get_p(f, total_people)
  42.             not_responded -= 1
  43.  
  44.         res += sum(get_p(x[1], total_people) for x in low_scores)
  45.  
  46.         print('Case #{}: {}'.format(case, res))
  47.  
  48. main()
Success #stdin #stdout 0.04s 9732KB
comments (?)
stdin
copy 
4
3 2
1 1
10 3
1 3 2
6 2
3 1
9 8
1 1 1 1 1 1 1 1
stdout
copy 
Case #1: 100
Case #2: 100
Case #3: 101
Case #4: 99
https://ideone.com/snAUxE
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!