I guess you'd probably want "res = 1 - (solveig + 0.0) / sum(ts)" as the penultimate line.
Sent from my iPad > On 22 Jun 2014, at 09:48, evandrix <evand...@gmail.com> wrote: > > Hi, > > I tried to run your solution through (using PyPy 2.3.1) A-large-practice, and > received the WA judgment on your output using that code. > > Is it meant to produce AC code through A-large-practice.in? > > Lee Wei > >> On Sunday, June 22, 2014 12:09:54 AM UTC+8, Eibe wrote: >> I just read the analysis for problem A of round 3 and it is mentioned that >> binary search is necessary for an O(n) solution. >> I don't think it is but maybe something with my thinking is wrong (I don't >> have a strict proof of correctness of the following): >> >> Let ts be a list, where ts[i] is the numbers of transistors in device i. >> >> Start with the following partition left, middle, right = [], ts, [] >> Now repeatedly move either the leftmost element of middle into left or the >> rightmost element of middle into right in a way that increases >> max(sum(left), sum(right)) in the least possible way. >> That is if sum(left) + middle[0] < sum(right) + middle[-1] move the leftmost >> otherwise the rightmost element (middle[-1] denotes the rightmost element of >> middle). >> >> I am a little sloppy here, but as we increase max(sum(left), sum(right)) by >> a minimal amount it feels that we will visit an optimal partition of ts >> eventually. >> >> In python code: >> T = int(raw_input()) >> for case in range(1, T+1): >> N, p, q, r, s = map(int, raw_input().split()) >> ts = [(i*p+q)%r+s for i in range(N)] >> c0, c1, c2 = 0, sum(ts), 0 >> a, b = 0, N >> solveig = sum(ts) >> while a < b: >> if c0 + ts[a] <= c2 + ts[b-1]: >> c0 += ts[a] >> c1 -= ts[a] >> a += 1 >> else: >> c2 += ts[b-1] >> c1 -= ts[b-1] >> b -= 1 >> solveig = min(solveig, max(c0, c1, c2)) >> res = 1 - solveig / sum(ts) >> print "Case #%i: %.10f" %(case, res) > > -- > 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 google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/869face2-2cb2-43c2-ab5c-b2555f010dad%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/7DF07896-3EF7-4BF5-9DD4-AA4FE20688F8%40pebody.org. For more options, visit https://groups.google.com/d/optout.
