Skip to content

Instantly share code, notes, and snippets.

@rubik
Last active December 16, 2015 17:39
Show Gist options
  • Save rubik/5471830 to your computer and use it in GitHub Desktop.
Save rubik/5471830 to your computer and use it in GitHub Desktop.
My solution to the problem A of the round 1A of Google Code Jam 2013
'''
Problem solution
----------------
The area of a circular ring is:
pi * (R^2 - r^2)
where R is the radius of the bigger circle and r
the radius of the other one.
Hence, the area of the k-th black ring is (with d
indicating the distance from the innermost circle,
i.e. d = 2k - 1):
pi * ((r + d)^2 - (r + d - 1)^2) =
= pi * (2r + 2d - 1)
= pi * (2r + 2(2k - 1) - 1)
= pi * (2r + 4k - 3)
If we now sum the areas of N consecutive rings (from k=1):
pi * (2r + 1)
pi * (2r + 5)
pi * (2r + 9)
...
...
we get:
N * pi * 2r + pi * (2N^2 - N) =
= pi * (2Nr + 2N^2 - N) =
= pi * (2N^2 + (2r - 1)N)
The sequence 1, 5, 9 is http://oeis.org/A016813, and its
sum is http://oeis.org/A000384.
We now equal this to pi * t, which is the maximum area
we can cover with paint:
pi * (2N^2 + (2r - 1)N) = pi * t
2N^2 + (2r - 1)N - t = 0
Applying the quadratic formula we finally get:
| 1 - 2r + sqrt(4r^2 - 4r + 1 + 8t) |
N = | ----------------------------------- |
|_ 4 _|
where |_x_| is the floor function.
'''
def sqrt(n):
'''The Newton method applied to sqrt().'''
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
def rings(r, t):
'''Returns the maximum number of complete rings one can draw,
starting with a central circle of radius `r` and `t` milliliters
of black paint.
'''
# We can discard the other solution (the one with the minus) since
# it would be either a negative value or less than the other one
# anyway.
return int((1 - 2 * r + sqrt(4 * r ** 2 - 4 * r + 1 + 8 * t)) // 4)
if __name__ == '__main__':
import sys
with open(sys.argv[1], 'w') as out:
total = int(sys.stdin.readline())
for i in range(1, total + 1):
r, t = map(int, sys.stdin.readline().split())
out.write('Case #{0}: {1}\n'.format(i, rings(r, t)))
@rubik
Copy link
Author

rubik commented Apr 27, 2013

Posted one hour after the contest finished, so I hope there won't be problems.

@Raffaello
Copy link

instead of use the formula with sqrt and PI that eliminate itslef:

milliter used = Rn^2 - Rn-1^2
Rn -> circle adius
Rn-1 -> prev circle radius.

R is incremented by 2 (cm)

so is somnething like this:
repeat until t>=0
ml = R^2 * (R-1)^2
.....
r = r+2

very simple.

@rubik
Copy link
Author

rubik commented Apr 27, 2013

Isn't that slow on big numbers? I mean, in the large input, r can go up to 10^18 and t to 2 * 10^18. With that method you'll need many iterations to find the final answer. With this method, on the other hand, you just solve a quadratic equation on the integers (so no floating point errors).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment