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
14.
15. def solve():
16. N, L = map(int, input().split())
17. C = list(map(int, input().split())) # of length L
18. remaining = N - sum(C)
19. if 100 % N == 0:
20. return 100
21. # print("Beginning langs chosen:", C)
22.
23. # 1) Generate the targets which round up
24. targets = [i for i in range(1, N) if isRoundUp(i, N)]
25. targets += [N]
26. least = targets[0] if len(targets) > 0 else N
27. # print("Targets:", targets)
28.
29. # 2) Find distance for each language from nearest target
30. diffs = [None for _ in range(L)] # diffs from each language to next
target
31. for i in range(L):
32. ind = bisect.bisect_left(targets, C[i])
33. diffs[i] = (targets[ind] - C[i], i)
34. # alternatively, use a heap (diffs, lang_ind)
35. diffs.sort()
36. # print("Diffs:", diffs)
37.
38. # 3) Allocate the persons, generating as many round ups as possible
39. for i in range(L):
40. margin, ind = diffs[i]
41. if margin >= least or remaining < margin: # we can just form new
language groups now
42. break
43. C[ind] += margin
44. remaining -= margin
45.
46. # 4) Calculate
47. total = sum(myRound(C[i], N) for i in range(L))
48. # deal with the remaining
49. total += (remaining // least) * myRound(least, N)
50. remaining = remaining % least
51. total += myRound(remaining, N)
52. # print("Final langs chosen:", C)
53. return total
54.
55.
56. T = int(input())
57. for t in range(T):
58. ans = solve()
59. 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.
For more options, visit https://groups.google.com/d/optout.
