PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Bullseye Solution: Google codejam 2013 Round 1A

(No Ratings Yet)

April 27, 2013 by puzzler 4 Comments

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1A 2013, top 1000 from this round will be eligible for next online round.

Problem

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:

  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.

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.

Limits

Small dataset

1 ≤ T ≤ 1000.
1 ≤ r, t ≤ 1000.

Large dataset

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

Sample

Input
5
1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000
Output
Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49

Solution with Java Code and Explanation

First we will calculate the area of the first black circle = π(r+1)^2 – πr^2 = π(2r+1);
Similarly area of the second black circle = π(r+1+2)^2 – π(r+1+1)^2 = π(2r+5);
Similarly area of the third black circle = π(r+1+4)^2 – π(r+1+3)^2 = π(2r+9);
This will form an AP with Tn = π((2r+1)+ (n-1)*4);
Sum of this AP Sn= n(a1 + an)/2 = nπ(2r+1 + 2r +1 + 4n -4)/2 = nπ(4r + 2 + 4n -4)/2 = π(2rn + 2n^2 -n)
We need to solve this sum for t => 2n^2 + n(2r-1) -t = 0
We can use quadratic solution for any ax^2 + bx +c = 0 = (-b +/- sqrt(b^2 – 4ac))/2, we can reject – options as it will become negative.
here a = 2, b = 2r -1 and c = -t

NOTE:- for writing the java code we have to use biginteger as the rang is too high and main problem you might face is to calculate square root of biginteger in java, this sample code below includes how you can calculate square root of biginteger in java.

Here is the Java code for Bullseye problem in Google codejam Online Round 1A 2013

package googlecodejam2013;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.math.BigInteger;

public class Bullseye {

	private static final BigInteger TWO = BigInteger.valueOf(2);

	private static boolean isSqrt(BigInteger n, BigInteger root)
	{
	    final BigInteger lowerBound = root.pow(2);
	    final BigInteger upperBound = root.add(BigInteger.ONE).pow(2);
	    return lowerBound.compareTo(n) <= 0
	        && n.compareTo(upperBound) < 0; 	} 	 	public static BigInteger sqrt(BigInteger n) 	{ 	    if (n.signum() >= 0)
	    {
	        final int bitLength = n.bitLength();
	        BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);

	        while (!isSqrt(n, root))
	        {
	            root = root.add(n.divide(root)).divide(TWO);
	        }
	        return root;
	    }
	    else
	    {
	        throw new ArithmeticException("square root of negative number");
	    }
	}

	public static String getCircleCount(BigInteger r, BigInteger t){
		BigInteger b = r.multiply(new BigInteger("2")).subtract(new BigInteger("1"));
		BigInteger a = new BigInteger("2");
		BigInteger ans = b.multiply(b).add(t.multiply(new BigInteger("8")));
		ans = sqrt(ans).subtract(b).divide(new BigInteger("4"));
		return ans.toString();
	}

	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("sample.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;

			File file = new File("sample.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				String line = bufReader.readLine();
				BigInteger r = new BigInteger(line.substring(0, line.indexOf(" ")));
				BigInteger t = new BigInteger(line.substring( line.indexOf(" ")+1));
				String output = getCircleCount(r, t);
				writer.write("Case #" + count + ": " + output+"\n");
				System.out.println("Case #" + count + ": " + output);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Facebook
Next Puzzle
Manage Your Energey Solution: Google codejam 2013 Round 1A

Checkout more Interview Questions Tags: Google codejam, Interview, Java, Solved Puzzles

Comments

  1. Altamir Gomes Bispo Junior says

    April 21, 2014 at 7:42 pm

    Another suggestion for avoiding overflows is to employ the bisection method with doable ranges.

    Reply
  2. Leandro says

    April 27, 2013 at 1:20 pm

    That’s ok. I got it.

    Reply
  3. Leandro says

    April 27, 2013 at 12:43 pm

    Hi,
    Ins’t the formula for circle area equals PI * (r)^2? Why is it necessary to subtract, like π(r+1)^2 – πr^2

    Thank you.

    Reply
    • Kthik says

      October 18, 2016 at 10:42 pm

      Because the area of the black paint isnt a full circle. It’s the difference between two circles.

      Reply

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Falling Diamonds Solution: Google codejam 2013 Round 1B
  • Bullseye Solution: Google codejam 2013 Round 1A
  • Dead Pixels solution: Facebook hacker cup 2013 Round 1
  • DS with insert, delete and getRandomElement in O(1)
  • Rotate an array by k elements
  • Objective Questions set C/C++ – Part 3
  • Find a pythagorean triplet from an array
  • Objective Questions set C/C++ – Part 2
  • 2nd smallest number from 32 numbers
  • Sort the array in O(N)

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous