Jolly Jumpers..~

Problem Statement
     
The Erdos number is a way of describing the "collaborative distance" between a scientist and Paul Erdos by authorship of scientific publications. Paul Erdos is the only person who has an Erdos number equal to zero. To be assigned a finite Erdos number, a scientist must publish a paper in co-authorship with a scientist with a finite Erdos number. The Erdos number of a scientist is the lowest Erdos number of his coauthors + 1. The order of publications and numbers assignment doesn't matter, i.e., after each publication the list of assigned numbers is updated accordingly. You will be given a vector <string> publications, each element of which describes the list of authors of a single publication and is formatted as "AUTHOR_1 AUTHOR_2 ... AUTHOR_N" (quotes for clarity only). Paul Erdos will be given as "ERDOS". Return the list of Erdos numbers which will be assigned to the authors of the listed publications. Each element of your return should be formatted as "AUTHOR NUMBER" if AUTHOR can be assigned a finite Erdos number, and just "AUTHOR" otherwise. The authors in your return must be ordered lexicographically.
Definition
   
Class:
ErdosNumber
Method:
calculateNumbers
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> calculateNumbers(vector <string> publications)
(be sure your method is public)
   
 
Notes
-
All authors mentioned in the list must be present in your return.
-
Assume that all publications of mentioned authors are given in publications.
-
String S is lexicographically before string T if S is a proper prefix of T, or if S has an earlier character at the first position where the strings differ.
Constraints
-
publications will contain between 1 and 50 elements, inclusive.
-
Each element of publications will contain between 1 and 50 characters, inclusive.
-
An author is a string of between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
-
Each element of publications will be a list of authors, separated by single spaces.
-
The authors in each element of publication will be distinct.
-
There will be at most 100 distinct authors in all publications.
-
Paul Erdos will be given as "ERDOS", and at least one publication will list him as one of the authors.
Examples
0)
 
   
{"ERDOS"}
Returns: {"ERDOS 0" }
The only author is Erdos himself, with Erdos number equal to 0.
1)
 
   
{"KLEITMAN LANDER", "ERDOS KLEITMAN"}
Returns: {"ERDOS 0", "KLEITMAN 1", "LANDER 2" }
publications[1] defines Kleitman's number as 1, and publications[0] defines Lander's number as 2.
2)
 
   
{"ERDOS A", "A B", "B AA C"}
Returns: {"A 1", "AA 3", "B 2", "C 3", "ERDOS 0" }
 
3)
 
   
{"ERDOS B", "A B C", "B A E", "D F"}
Returns: {"A 2", "B 1", "C 2", "D", "E 2", "ERDOS 0", "F" }
E has coauthors B (Erdos number 1) and A (Erdos number 2), so his Erdos number is defined through the coauthor with the lowest Erdos number. D and F aren't connected to Erdos and thus have no numbers assigned.
4)
 
   
{"ERDOS KLEITMAN", "CHUNG GODDARD KLEITMAN WAYNE", "WAYNE GODDARD KLEITMAN",
 "ALON KLEITMAN", "DEAN GODDARD WAYNE KLEITMAN STURTEVANT"}
Returns:
{"ALON 2",
 "CHUNG 2",
 "DEAN 2",
 "ERDOS 0",
 "GODDARD 2",
 "KLEITMAN 1",
 "STURTEVANT 2",
 "WAYNE 2" }
 
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Cantor dust is a 2-dimensional fractal constructed in the following way. Initially the fractal is a black square. At each iteration, each square of the fractal is divided into a 3x3 subgrid of equal subsquares. Any black subsquares which belong to the middle row or to the middle column of a subgrid (or to both of them) are painted white. You are given a vector <string> pattern which represents a rectangular pattern of black and white squares (represented by 'X' and '.' characters, respectively). Return the number of occurrences of this pattern in Cantor dust at iteration time. Overlapping occurrences are allowed.
Definition
   
Class:
CantorDust
Method:
occurrencesNumber
Parameters:
vector <string>, int
Returns:
int
Method signature:
int occurrencesNumber(vector <string> pattern, int time)
(be sure your method is public)
   
 
Constraints
-
time will be between 1 and 9, inclusive.
-
pattern will contain between 1 and min(50, 3time) elements, inclusive.
-
Each element of pattern will contain between 1 and min(50, 3time) characters, inclusive.
-
All elements of pattern will contain the same number of characters.
-
Each character in each element of pattern will be '.' or 'X'.
Examples
0)
 
   
{".X",".."}
1
Returns: 1
 
1)
 
   
{".."}
1
Returns: 2
 
2)
 
   
{"."}
2
Returns: 65
 
3)
 
   
{"X...X"}
2
Returns: 4
 
4)
 
   
{"X"}
9
Returns: 262144
 
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
A robot needs to climb a flat vertical wall with several handholds on it.  The robot has four mechanial "hands". Each hand can grab a handhold positioned anywhere within or on the boundary of a circle of radius armLength from robot's center. While the robot is climbing the wall, three of the hands have to remain anchored at three distinct handholds at all times. To move between holding positions, the robot can use the fourth hand to grab next handhold and release one of the previous handholds. At the start of the climb the robot can stand on one of its hands anywhere on the ground. Thus, it can grab any single handhold which is not higher than 2*armLength from the ground, and to start climbing it must grab three handholds while still standing on the fourth hand.  The wall is described as a plane with a cartesian coordinate system on it. The ground is the line y = 0. Handhold i is positioned at the point (holdx[i], holdy[i]).  Return the y-coordinate of the highest point the robot can reach with a hand while standing on the ground or hanging on the wall using the other three hands.
Definition
   
Class:
WallClimbing
Method:
maxHeight
Parameters:
vector <int>, vector <int>, int
Returns:
double
Method signature:
double maxHeight(vector <int> holdx, vector <int> holdy, int armLength)
(be sure your method is public)
   
 
Notes
-
The robot can't grab one handhold with two or more hands.
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
holdx will contain between 1 and 16 elements, inclusive.
-
holdy will contain the same number of elements as holdx.
-
Each element of holdx and holdy will be between 1 and 1000, inclusive.
-
The location of each handhold will be distinct.
-
handLength will be between 1 and 100, inclusive.
Examples
0)
 
   
{10, 10, 10}
{20, 40, 60}
30
Returns: 80.0
The three handholds are arranged in a vertical line, and it is possible to hang on them and reach 80.0.
1)
 
   
{20, 40, 60, 80}
{20, 20, 20, 20}
20
Returns: 40.0
The four handholds are arranged in a horizontal line. It is possible to hang on any three successive handholds, but this doesn't let the robot reach higher than from the ground.
2)
 
   
{10, 10, 10, 10,  10,  10,  10,  10,  10}
{20, 40, 60, 80, 100, 120, 140, 160, 180}
30
Returns: 200.0
Each triple of successive handholds is a valid holding position, and it is possible to get to the triple {6,7,8} and reach a height of 200.
3)
 
   
{10, 10}
{10, 20}
40
Returns: 80.0
There are not enough handholds to hang on them.
4)
 
   
{ 50, 100, 150, 200,
  50, 100, 150, 200,
  50, 100, 150, 200,
  50, 100, 150, 200}
{ 50,  50,  50,  50,
 100, 100, 100, 100,
 150, 150, 150, 150,
 200, 200, 200, 200}
25
Returns: 50.0
Here no three handholds are close enough together for the robot to hang from them.
5)
 
   
{ 50, 100, 150, 200,
  50, 100, 150, 200,
  50, 100, 150, 200,
  50, 100, 150, 200}
{ 50,  50,  50,  50,
 100, 100, 100, 100,
 150, 150, 150, 150,
 200, 200, 200, 200}
50
Returns: 250.0
The robot can move to the highest row and hang on a horizontal triple.
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)2003, TopCoder, Inc. All rights reserved.