I would be astonished to discover that the different languages had different test cases. IMO it's more likely that Python2 has a different native round method, or that the math leading up to the call to round() was executed in a way that caused a different result.
On Tue, May 1, 2018 at 12:47 PM Xiongqi ZHANG <[email protected]> wrote: > I think the test case are different for python2/3 for some reason. If we > run the code in python2 against the test case set up for python3, it might > failed as well. > > Bartholomew Furrow <[email protected]>于2018年5月1日周二 上午11:20写道： > >> 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 >> <https://groups.google.com/d/msgid/google-code/CAHaiWHMzCU9pUp%3D5QKinwzaKXMGUrH1pkLDyZivBGm3Xnis%3DYQ%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/CAGDEU-LfJofyMdcPErWOp-My0DgLpo%2BZiZqeH_sMzzxLzuNfWw%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAGDEU-LfJofyMdcPErWOp-My0DgLpo%2BZiZqeH_sMzzxLzuNfWw%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/CAHaiWHMJUPYJxZ1D%3DU089cQo0zQn%3DY7MnXDg9BC6giTGsx0Jcw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
