I used the following logic for the problem - Let k be the required answer. Then, (R+1)^2 - R^2 = 2R + 1 amount of paint to paint the first circle (R+3)^2 - (R+2)^2 = 2R + 5 amount of paint to paint the second circle. ... and so on - we get total k equations.
Now, adding the k equations, and putting the RHS <= t we get the following quadratic inequality: 2k^2 + (2R - 1)k - t <= 0. So I managed to get a closed formula for this problem. However, when I ran my code to the test cases given, it solved them all correctly, except for the last one. I double checked my soln; seemed there was nothing at all but a problem in Python (I think.). Substituting k = 49 works, but k = 50 in (*) makes RHS > 0. [Check the following code] >>> def check(k): r,t = 10000000000000000, 1000000000000000000 if 2*k*k + 2*(r-1)*k - t <= 0: return True return False >>> check(49) True >>> check(50) False >>> r,t = 10000000000000000, 1000000000000000000 >>> (-(2*r - 1) + pow(pow((2*r - 1), 2) + 4*2*t, 0.5))/4.0 ## Note that this is the closed formula. 50.0 I wonder what's causing such error? Is it because of calculation of big numbers? Anyhow, in seeing this I managed to submit for A small. I changed my code abit using while loop and tweaking alittle and submitted large; but got it wrong in the end. I'm currently using Python 2.7. Any reason why its behaving so weirdly? -- 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]. For more options, visit https://groups.google.com/groups/opt_out.
