Bullseye: Google Code Jam 2013 Round 1A

This problem appeared in Round 1A of Google Code Jam 2013. Here’s the problem description:

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 milliliters of black paint, which she will use to draw rings of thickness 1 cm (one centimeter). A ring of thickness 1 cm is the space between two concentric circles whose radii differ by 1 cm.

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:

  1. Maria imagines a white ring of thickness 1cm around the last black ring.
  2. 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.


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


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


Small dataset

1 ≤ T ≤ 1000.
1 ≤ rt ≤ 1000.

Large dataset

1 ≤ T ≤ 6000.
1 ≤ r ≤ 1018.
1 ≤ t ≤ 2 × 1018.


1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000

Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49


The problem can be solved with discrete binary search. The key idea is that the amount of paint used always increases with the number of rings. At some point, it gets larger than the amount of paint available, ‘t’ and from then on, painting any more rings is infeasible. The amount of paint used for painting first ‘x’ rings turns out to be (x + 1)*(2*r + 2*x + 1) so deciding if first ‘x’ rings can be painted with paint ‘t’ can be done in O(1) time.

bool infeasible(unsigned long long x) {
    return (x + 1)*(2*r + 2*x + 1) > t;

For small values of ‘x’, the solution is feasible. At some large value of x, it becomes infeasible and remains infeasible for all larger values of x. We need to find the smallest x for which the solution is infeasible.

Take a look at the C++ implementation.

Try your hand at problems EKOKOPC12A and IMMERSED, which use this idea.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s