JOIN
Get Time

   Problem Statement  

 Problem Statement for CirclesGame

Problem Statement

    Alice is playing a game with her old friend, Bob.

There are n circles on a paper. The center of the i-th circle is (x[i], y[i]), and the radius is r[i]. No two different circles share a common point on their boundary. However, it is allowed for circles to be located entirely within other circles. In the game, the players take alternating turns. Alice starts. In each move, the current player must:
  1. Choose a circle such that there is no red point strictly inside the circle.
  2. Pick one point that is strictly inside the chosen circle and color it red.
If a player can't do such a move, he/she loses the game.

You are given the int[]s x, y, and r that describe a set of circles with the above property. Return "Alice" (quotes for clarity) if Alice has a winning strategy for the given set of circles. Otherwise, return "Bob".
 

Definition

    
Class:CirclesGame
Method:whoCanWin
Parameters:int[], int[], int[]
Returns:String
Method signature:String whoCanWin(int[] x, int[] y, int[] r)
(be sure your method is public)
    
 

Notes

-Points located on the boundary of a circle are not considered to be strictly inside that circle.
 

Constraints

-x will contain between 1 and 50 elements, inclusive.
-x, y, and r will each contain the same number of elements.
-Each element in x will be between -10,000 and 10,000, inclusive.
-Each element in y will be between -10,000 and 10,000, inclusive.
-Each element in r will be between 1 and 10,000, inclusive.
-No two circles intersect. That is, the boundaries of the given circles are pairwise disjoint.
 

Examples

0)
    
{0}
{0}
{1}
Returns: "Alice"
This test case has just one circle. Alice draws a red point anywhere inside the circle and Bob has no valid move.
1)
    
{0, 3}
{0, 0}
{1, 1}
Returns: "Bob"
Two separate circles. Alice draws a red point in one of them, Bob draws a red point in another one, then Alice has no valid moves.
2)
    
{0, 0, 5}
{0, 0, 0}
{1, 2, 1}
Returns: "Alice"
In her first move, Alice should draw a point within the circle 1, but so that it's not within the circle 0. (Both indices are 0-based.)
3)
    
{0, 0, 0, 10, 10, 20}
{0, 0, 0, 0, 0, 0}
{1, 2, 3, 1, 2, 1}
Returns: "Bob"
4)
    
{10,20,30,40,50,60,70,80}
{8,7,6,5,4,3,2,1}
{2,2,2,2,2,2,2,2}
Returns: "Bob"
5)
    
{0, 3, 6, 9, 12, -4747, -4777}
{-5858, -5858, -5858, -5858, -5858, 777, 777}
{58, 1, 1, 1, 1, 44, 8}
Returns: "Bob"
6)
    
{5202, 5699, -7433, 5068, -9483, -684, -6593, 5108, -7813, 6823, 3267, -8222, -8547, 2878, 2413, 8557, 5149, 5073, -8638, -6108, 8097}
{8728, -7407, 4338, -8414, 7652, -3705, -984, 5976, -9180, -9119, 9301, 2398, 7915, 6205, 7665, 717, -9884, 11, -8579, -6903, -746}
{4196, 9303, 7152, 5875, 2943, 788, 502, 416, 1958, 3174, 182, 1256, 1147, 444, 979, 65, 1040, 1233, 438, 175, 1140}
Returns: "Alice"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 561 Round 1 - Division I, Level Two