4
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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}$$

$\endgroup$
1
  • $\begingroup$ That explains where the formula is coming from, thanks. $\endgroup$ Commented May 1, 2013 at 18:46
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.