I'm surprised it worked in Python2! Generally if rounding exactly is an important part of the problem, you should do everything in integers. Actually, for most problems, you should do everything you can in integers if it's possible.
On Tue, May 1, 2018 at 11:41 AM Xiongqi ZHANG <[email protected]> wrote: > I submitted almost the same code for python2, and it was accepted. > But it keeps failing for python3. > > Looks like the floating point arithmetic is the problem. > I rewrite the logic for round() and it get accepted. > > > 1. import bisect > 2. > 3. def isRoundUp(a, b): > 4. a = 100 * a % b > 5. if a * 2 >= b: > 6. return True > 7. return False > 8. > 9. def myRound(a, b): > 10. base = 100 * a // b; > 11. if isRoundUp(a, b): > 12. base = base + 1 > 13. return base > > > 1. > 2. def solve(): > 3. N, L = map(int, input().split()) > 4. C = list(map(int, input().split())) # of length L > 5. remaining = N - sum(C) > 6. if 100 % N == 0: > 7. return 100 > 8. # print("Beginning langs chosen:", C) > 9. > 10. # 1) Generate the targets which round up > > > 1. targets = [i for i in range(1, N) if isRoundUp(i, N)] > > > 1. targets += [N] > 2. least = targets[0] if len(targets) > 0 else N > 3. # print("Targets:", targets) > 4. > 5. # 2) Find distance for each language from nearest target > 6. diffs = [None for _ in range(L)] # diffs from each language to next > target > 7. for i in range(L): > 8. ind = bisect.bisect_left(targets, C[i]) > 9. diffs[i] = (targets[ind] - C[i], i) > 10. # alternatively, use a heap (diffs, lang_ind) > 11. diffs.sort() > 12. # print("Diffs:", diffs) > 13. > 14. # 3) Allocate the persons, generating as many round ups as possible > 15. for i in range(L): > 16. margin, ind = diffs[i] > 17. if margin >= least or remaining < margin: # we can just form new > language groups now > 18. break > 19. C[ind] += margin > 20. remaining -= margin > 21. > 22. # 4) Calculate > > > 1. total = sum(myRound(C[i], N) for i in range(L)) > > > 1. # deal with the remaining > > > 1. total += (remaining // least) * myRound(least, N) > > > 1. remaining = remaining % least > > > 1. total += myRound(remaining, N) > > > 1. # print("Final langs chosen:", C) > 2. return total > 3. > 4. > 5. T = int(input()) > 6. for t in range(T): > 7. ans = solve() > 8. print("Case #{}: {}".format(t+1, ans)) > > > > > Jeffrey Yun <[email protected]>于2018年5月1日周二 上午9:37写道： > >> # 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. >> > -- > 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-JFfHWoto05TovKrt%2BZaSd5dpkPuVam9tLaOKbTPKWgbA%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAGDEU-JFfHWoto05TovKrt%2BZaSd5dpkPuVam9tLaOKbTPKWgbA%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/CAHaiWHMzCU9pUp%3D5QKinwzaKXMGUrH1pkLDyZivBGm3Xnis%3DYQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
