In Sample Case #3, one optimal scenario is as follows: each of the remaining two people chooses an unchosen language, so the rounded percentages add up to 50 + 17 + 17 + 17 = 101.
if 5 people chooses same language and one person chooses different one then the result=102 5*17+17=102 Regards On Wed, May 2, 2018 at 3:49 AM, Xiongqi ZHANG <[email protected]> wrote: > while num * 100 / N - int(num * 100 / N) < 0.5: > num += 1 > > This is too slow for large input. Instead you can calculate the least > number to get a round up. > > > 1. for T in range(int(input())): > 2. N, L = list(map(int, input().split())) > 3. C = list(map(int, input().split())) > 4. > 5. if 100 % N != 0: > 6. remaining = N - sum(C) > 7. counts = C + [0 for i in range(remaining)] > 8. > 9. least = 0 > 10. while least * 100 / N - int(least * 100 / N) < 0.5: > 11. least += 1 > 12. needed = [] > 13. for cnt in counts: > 14. if cnt <= least: > 15. needed.append(least - cnt) > 16. else: > 17. num = cnt > 18. while num * 100 / N - int(num * 100 / N) < 0.5: > 19. num += 1 > 20. needed.append(num - cnt) > 21. > 22. needed, counts = list(map(list, zip(*sorted(zip(needed, counts))))) > 23. > 24. for i in range(len(counts)): > 25. if needed[i] <= remaining: > 26. counts[i] += needed[i] > 27. remaining -= needed[i] > 28. counts[-1] += remaining > 29. > 30. result = [] > 31. for cnt in counts: > 32. percentage = cnt * 100 / N > 33. if percentage - int(percentage) < 0.5: > 34. result.append(int(percentage)) > 35. else: > 36. result.append(int(percentage) + 1) > 37. > 38. print('Case #' + str(T + 1) + ': ' + str(sum(result))) > 39. > 40. else: > 41. print('Case #' + str(T + 1) + ': 100') > > > Arti Schmidt <[email protected]>于2018年5月1日周二 下午1:41写道： > >> My solution passed both visible test sets, but I got a >> "TIME_LIMIT_EXCEEDED" error on the hidden one. As far as I can tell, I did >> exactly what was described to solve test set 3 in the analysis. What did I >> do wrong? >> >> (Python 3) >> >> for T in range(int(input())): >> N, L = list(map(int, input().split())) >> C = list(map(int, input().split())) >> >> if 100 % N != 0: >> remaining = N - sum(C) >> counts = C + [0 for i in range(remaining)] >> >> needed = [] >> for cnt in counts: >> num = cnt >> while num * 100 / N - int(num * 100 / N) < 0.5: >> num += 1 >> needed.append(num - cnt) >> >> needed, counts = list(map(list, zip(*sorted(zip(needed, >> counts))))) >> >> for i in range(len(counts)): >> if needed[i] <= remaining: >> counts[i] += needed[i] >> remaining -= needed[i] >> counts[-1] += remaining >> >> result = [] >> for cnt in counts: >> percentage = cnt * 100 / N >> if percentage - int(percentage) < 0.5: >> result.append(int(percentage)) >> else: >> result.append(int(percentage) + 1) >> >> print('Case #' + str(T + 1) + ': ' + str(sum(result))) >> >> else: >> print('Case #' + str(T + 1) + ': 100') >> >> -- >> 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/c7efd9ae-a678-476d-b579-e64bf35c6514%40googlegroups.com >> . >> For more options, visit https://groups.google.com/d/optout. >> > -- > 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/CAGDEU-%2BX6-%3DbtSAyjD%3Dc2KnE3NU2xa_ > U8CmmLqhrhmtqLRGLkg%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAGDEU-%2BX6-%3DbtSAyjD%3Dc2KnE3NU2xa_U8CmmLqhrhmtqLRGLkg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > For more options, visit https://groups.google.com/d/optout. > -- 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/CAH5vfnPjJx5Aq783sutRk3aj_UxJ_MATNh9fh8MnPyKUQxxtSQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
