Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem below appeared on the latest round of Google Code Jam:


Maria has been hired by the Ghastly Chemicals Junkies (GCJ) company to help them manufacture bullseyes. A bullseye consists of a number of concentric rings (rings that are centered at the same point), and it usually represents an archery target. GCJ is interested in manufacturing black-and-white bullseyes.

Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm. Then she repeats the following process for as long as she has enough paint to do so:

Maria imagines a white ring of thickness 1cm around the last black ring. Then she draws a new black ring of thickness 1cm around that white ring. Note that each "white ring" is simply the space between two black rings. The area of a disk with radius 1cm is π cm2. One millilitre of paint is required to cover area π cm2. What is the maximum number of black rings that Maria can draw? Please note that:

  • Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.
  • There will always be enough paint to draw at least one black ring.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a line containing two space separated integers: r and t.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of black rings that Maria can draw.

**Sample Input**    
5
1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000


**Sample Output**  
Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49

The inputs were very large, so a brute force approach wouldn't solve it in time. I looked at the top solutions, and most used a variation of the formula below:

2*R*X + (2*X-1)*X <= T

where R is the radius of the first white circle, X is the total number of rings she can paint, and T is the milliliters of ink she has available. To find the answer you would basically do a binary search looking for the highest X that would make the equation true.

My question: Where does that formula come from? Is it possible to explain how come this solves the problem, in simple terms? Any light you can shed will be appreciated.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

The annulus with radii $r_1<r_2$ has area $\pi(r_2^2-r_1^2)$. So it requires $r_2^2-r_1^2$ milliliters of paint. When $r_2-r_1=1$, we have that $r_2^2-r_1^2=(r_2-r_1)(r_2+r_1)=r_2+r_1=2r_1+1$.

Now, if your $n$th black strip is an annulus with radii $r_1(n)=r+2(n-1)$ and $r_2(n)=r_1(n)+1$, and the paint required is $$2r_1(n) +1= 2r + 1 + 4(n-1)$$

So, after $M$ stripes, she will have used up:

$$\sum_{n=1}^M \left(2r+1+4(n-1)\right)=(2r+1)M + 4\frac{M(M-1)}{2}=2rM + M(2M-1)$$

Also, a binary search isn't necessary. You can just solve the equation:

$$2x^2+(2r-1)x-T=0$$ and take the largest integer less than the larger root. That larger root is:

$$\frac{1-2r+\sqrt{(2r-1)^2+8T}}{4}$$

share|improve this answer
    
That explains where the formula is coming from, thanks. –  DanielS May 1 '13 at 18:46

If the inner radius of a ring is $r$ and the outer radius is $r+1$, the area of the ring is $\pi(r+1)^2-\pi r^2=\pi (2r+1)$, so the ring takes $2r+1$ milliliters of paint. The next ring is $2$cm greater in radius (one black, one white), so takes 2(r+2)+1 milliliters. To paint $x$ rings starting at $r$ takes $2r+1+2(r+2)+1+2(r+4)+1+\ldots 2(r+2x-2)+1=\sum_{i=0}^{x-1}(2r+4i+1)=2rx+2x(x-1)+x=2rx+2x^2-x$

Then you don't need to do a binary search. You can just solve the quadratic for $x$ and round down.

share|improve this answer
    
Thanks, that helped. –  DanielS May 1 '13 at 18:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.