TopCoder.com Algorithm Problems Searcher



Found 36 results

FractalPicture

Brute Force, Geometry, Recursion, Simple Math, Simulation



Used in:

SRM 500

Used as:

Division I Level Two

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , Smylic

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11344

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14429&pm=11344

Problem Statement

    Nick likes to draw fractals. For the special occasion of Single Round Match 500, he decided to draw the 500th generation of his favorite fractal.



Each generation of the fractal can be described as a set of segments on the plane. Some of these segments are called final and all other are considered to be non-final. In each non-final segment, one of its endpoints is chosen and called the root of this segment. In pictures below, solid and dotted lines are used to represent final and non-final segments, correspondingly.



The first generation consists of one segment with endpoints (0, 0) and (0, 81). This segment is non-final and its root is (0, 0).







The i-th generation, i >= 2, is produced from the (i-1)-th generation as follows. All final segments from the (i-1)-th generation are included into the i-th generation without any changes. For each non-final segment from the (i-1)-th generation, let A and B be its endpoints, with A being its root. The following steps are then done:
  • The point C is drawn on the segment AB so that the length of segment AC is twice as large as the length of segment BC.
  • Segment CD is drawn as the rotation of segment CB around point C by 90 degrees clockwise.
  • Segment CE is drawn as the rotation of segment CB around point C by 90 degress counter-clockwise.
  • Segment AC is included in the i-th generation as a final segment.
  • Segments CB, CD and CE are included in the i-th generation as non-final segments. The root of each of these three segments is point C.
The second and third generations of this fractal are shown on the picture below.



 



Consider a rectangle R on the plane that consists of points (x, y), such that x1 <= x <= x2 and y1 <= y <= y2. Let S be the set of all segments of the 500-th generation of the fractal described above (both final and non-final ones). Return the total length of all parts of segments from S that belong to rectangle R.
 

Definition

    
Class:FractalPicture
Method:getLength
Parameters:int, int, int, int
Returns:double
Method signature:double getLength(int x1, int y1, int x2, int y2)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-x1 will be between -100 and 100, inclusive.
-x2 will be between x1+1 and 100, inclusive.
-y1 will be between -100 and 100, inclusive.
-y2 will be between y1+1 and 100, inclusive.
 

Examples

0)
    
-1
0
1
53
Returns: 53.0
Only one part of fractal segments belongs to this rectangle: (0, 0) - (0, 53).
1)
    
1
1
10
10
Returns: 0.0
No parts of fractal segments belong to this rectangle.
2)
    
-10
54
10
55
Returns: 21.0
Two parts of fractal segments belong to this rectangle: (-10, 54) - (10, 54) and (0, 54) - (0, 55). Note that parts that lie on the rectangle's border also belong to the rectangle.
3)
    
14
45
22
54
Returns: 2999.0

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.

SubgraphIsomorphism

Graph Theory



Used in:

TCO10 Round 3

Used as:

Division I Level One

Writer:

Unknown

Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11016

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14274&pm=11016

Problem Statement

    In this problem you will be given a large graph formed by a random process. You will then be asked to find a series of subgraphs of ever-increasing size. Your task is to answer as many queries as possible before time runs out.



An undirected graph G = (V,E) is defined by a set of vertices, V, indexed from 0 to N-1 and a set of edges (u,v). As the graph is undirected, each edge will be listed in both directions. An induced subgraph H of G is defined by a subset of vertices V' and all of the edges in E where both u and v are in V'. See Wikipedia for a more rigorous definition.



In the induced subgraph isomorphism problem, you are given two graphs: a graph G with N vertices, and a graph H with K vertices. Your task is to find a mapping f() from 0..K-1 to 0..N-1 such that (u,v) is an edge in H if and only if (f(u), f(v)) is an edge in G. Again, see Wikipedia for a formal definition.



In this problem, you will be given a graph G, followed by a series of smaller graphs H5, H6, H7, ... (starting from H5 intentionally). Hi will be an induced subgraph of G on i vertices. For each such query, you should return a int[] with i elements, where element j of your return represents f(j) above.



Each graph input will be formatted as a single int[]. The first element of the array will give the number of vertices. The degrees of the nodes will then be listed one at a time, along the their lists of neighbors. Thus, the following pseudocode will decode the input: 
	ptr = 0
	vertices = input[ptr++]
	for (i = 0; i < vertices; i++) 
		degree = input[ptr++]
		for (j = 0; j < degree; j++) 
			createEdge(i, input[ptr++])
where createEdge(u,v) creates an edge in whatever data structure you choose to use.



Scoring

You will be given 10 seconds of total execution time. A function initialize will take the large graph G, and should return an integer (it doesn't matter what you return here). A function query will then be called repeatedly, starting with H5. Your 10 seconds includes the time spent in these functions (both initialize and query). Your query function will be called until you either run out of time, or give an incorrect return (one that isn't a match, or isn't valid). Your score for each test case will simply be the number of queries answered correctly before time runs out (or an incorrect return). Your overall score for all test cases will be the sum of your scores on all the individual test cases.

Test Generation

The graph G will be generated by first picking three values: N, alpha, and D. N will be chosen uniformly at random in [1000,20000]. Alpha will be a floating point number uniformly at random in [1,3). D will be an integer chosen uniformly in [2,30].



For vertex i, a location (xi,yi) will be chosen with xi and yi each integers in [0,220). For each vertex i, we will then generate D undirected edges (i,j). Given a choice of i, each j will be chosen with probability proportional to (1+dist(i,j))-alpha, where dist(i,j) = sqrt((xi-xj)2 + (yi-yj)2). The choices of j will be made with replacement, so the same j may be chosen multiple times. After all selection are made, duplicates are eliminated, leaving a simple undirected graph.



To select each Hi, a seed vertex u will be chosen uniformly at random from the N vertices in G. All neighbors of u will be added to the set of frontier vertices. Then, a node is chosen randomly from the set of frontier vertices and all of its neighbors are added to the frontier. A node added to the frontier multiple times will have multiple chances to be selected (making the frontier a multiset). This process is repeated until i vertices are chosen. If the frontier set becomes empty before i vertices have been selected, the select process is restarted from scratch. Finally, the subgraph is extracted and the vertex labels are randomly shuffled.

Offline Tool

An offline testing tool is provided here.
 

Definition

    
Class:SubgraphIsomorphism
Method:initialize
Parameters:int[]
Returns:int
Method signature:int initialize(int[] G)
 
Method:query
Parameters:int[]
Returns:int[]
Method signature:int[] query(int[] H)
(be sure your methods are public)
    
 

Notes

-The time limit is 10 seconds.
-The memory limit is 1024MB.
-Your method will be queried until you run out of time, or until the size of the subgraph is equal to the largest connected component in G.
-There are 50 test cases.
 

Examples

0)
    
"1"
Returns: "seed = 1<br>
N = 13878<br>
alpha = 2.178079240820598<br>
deg = 9<br>
"
1)
    
"2"
Returns: "seed = 2<br>
N = 19425<br>
alpha = 1.8807096080672547<br>
deg = 16<br>
"
2)
    
"3"
Returns: "seed = 3<br>
N = 7403<br>
alpha = 2.6339482751431706<br>
deg = 21<br>
"
3)
    
"4"
Returns: "seed = 4<br>
N = 11809<br>
alpha = 2.743153197688343<br>
deg = 4<br>
"
4)
    
"5"
Returns: "seed = 5<br>
N = 15638<br>
alpha = 1.8666642015582442<br>
deg = 7<br>
"
5)
    
"6"
Returns: "seed = 6<br>
N = 13268<br>
alpha = 2.9672762511627835<br>
deg = 30<br>
"
6)
    
"7"
Returns: "seed = 7<br>
N = 6674<br>
alpha = 1.726463701449059<br>
deg = 8<br>
"
7)
    
"8"
Returns: "seed = 8<br>
N = 18559<br>
alpha = 1.8207492412680386<br>
deg = 27<br>
"
8)
    
"9"
Returns: "seed = 9<br>
N = 2650<br>
alpha = 2.3528908831563458<br>
deg = 12<br>
"
9)
    
"10"
Returns: "seed = 10<br>
N = 2706<br>
alpha = 1.545583100723283<br>
deg = 5<br>
"

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.

RightTriangle

Math, Search



Used in:

SRM 473

Used as:

Division I Level Two

Writer:

misof

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10976

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14155&pm=10976

Problem Statement

    

Consider a circle in the plane.

You are given an int places. This is the number of places that are equally spaced along the perimeter of the circle, i.e., the distance between any two consecutive places is equal. The places are numbered 0 to places-1 in clockwise order, starting at an arbitrary place.

We will now draw red points in some of the places. The number of red points is given as an int points. As the number of points may be large, we will generate them using a simple process that is described below.

Finally, once all points are generated, your task is to find and return the number of right triangles that have all three vertices in red points.

To generate the points, you are given three ints a, b, and c. For n = 0, 1, 2, 3, ..., points-1, execute the following steps:

  • Compute P[n] = (a*n*n + b*n + c) modulo places.
  • Starting at P[n], find the first place in the clockwise direction that does not contain a red point.
  • Put a red point onto that place.
 

Definition

    
Class:RightTriangle
Method:triangleCount
Parameters:int, int, int, int, int
Returns:long
Method signature:long triangleCount(int places, int points, int a, int b, int c)
(be sure your method is public)
    
 

Notes

-A right triangle is a triangle with non-zero area in which one of the angles is exactly 90 degrees.
-For any valid input the answer fits into a long (i.e., a signed 64-bit integer variable).
 

Constraints

-places will be between 1 and 1,000,000, inclusive.
-points will be between 0 and 100,000, inclusive.
-points will not be greater than places.
-a will be between 0 and 1,000,000, inclusive.
-b will be between 0 and 1,000,000, inclusive.
-c will be between 0 and 1,000,000, inclusive.
 

Examples

0)
    
9
3
0
3
0
Returns: 0
The points are placed on places 0, 3, and 6. The resulting triangle is not a right triangle (in fact, it is equilateral).
1)
    
40
3
5
0
0
Returns: 1
This time the red points are on places 0, 5, and 20. The only triangle determined by these points is a right triangle.
2)
    
4
4
16
24
17
Returns: 4
This time the formula for the next place always gives the output 1. Hence the points are placed on places 1, 2, 3, and 0, in this order. Each of the four triangles determined by these points is a right triangle.
3)
    
1000000
47000
0
2
5
Returns: 0
An awful lot of obtuse triangles.
4)
    
200000
700
123456
789012
345678
Returns: 6980
Watch out for integer overflow when computing P[n].

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.

BrokenClayTile

Brute Force



Used in:

NSA 3 US

Used as:

Division I Level One

Writer:

Unknown

Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10756

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14207&pm=10756

Problem Statement

    An ancient clay tile was found during an archeological dig. It could have been an important find, but unfortunately it is broken into pieces which are shuffled and shabby, so in its current state it has hardly any importance. You have to reconstruct the original look of the tile from its pieces.



The original tile is generated as a highly symmetrical shape which fits inside of an S x S square. This is done as follows: one eighth of the tile is generated as a random polygon. Then the polygon is filled with random pattern, created as a set of lines of random orientation and width. Finally, the generated one eighth of the tile is reflected symmetrically with respect to axes x=y and the result is rotated by 90 degrees three times to fill all the tile. See the visualizer source code for more details.



The generated tile is broken into pieces using a Voronoi diagram of a random set of points within the tile. Some of these pieces are removed, and the edges of the rest are crumbled up randomly. Note that the original edges of the tile generally don't crumble: the pixels on them can crumble if they belong to the border of the S x S square and to the crack between two pieces at the same time, or if after the main crumbling process they have 1 or 0 pixels of the same piece adjacent to them.



Finally, the resulting pieces are rotated randomly and presented to you as a String[] pieces. The format of pieces is as follows: each piece is a sequence of individual Strings representing its rows, and the consecutive pieces are separated with "-" Strings. The pixels where there is no clay are represented with '.', and black and white clay pixels are represented with '1' and '0' characters, respectively. Besides, you are given S - the size of the square and N - the number of pixels in the original tile.



Your task is to restore the original tile as an S x S square, with black and white pixels represented in the same way as in the input. You have to arrange the pieces in some way and fill the spaces between them with clay pixels of any color. Note that you don't need to distinguish the parts which are covered with the actual pieces from the parts which are lost or crumbled, you only have to reconstruct the whole image as close to the original one as possible.



Your score for an individual test case will be calculated as follows: the original tile and the one you returned are compared pixel-by-pixel; for each pixel which is absent ('.') on both tiles or present on both tiles in the same color you score 1, and for each pixel which is present on both tiles but has different colors you score 0.5. Finally, the sum of scores for individual pixels is divided by S*S. Your overall score will be the sum of scores over all test cases. A visualizer is available for visualization and offline testing.
 

Definition

    
Class:BrokenClayTile
Method:reconstruct
Parameters:int, int, String[]
Returns:String[]
Method signature:String[] reconstruct(int S, int N, String[] pieces)
(be sure your method is public)
    
 

Notes

-Invalid return (i.e., sized not S x S or containing characters other than '.', '0' and '1') gives you a score of 0.
-Please see visualizer source for details of test case generation.
-The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). There is no explicit code size limit.
-There are 10 example test cases and 100 full submission test cases.
 

Constraints

-S will be up to 401.
-Up to one fifth of the pieces will be removed.
 

Examples

0)
    
"1"
Returns: 
"seed = 1<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/1_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/1_broken.png>"
S = 361

N = 44856

157 pieces generated.

140 pieces passed to the solution.
1)
    
"2"
Returns: 
"seed = 2<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/2_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/2_broken.png>"
S = 381

N = 142348

504 pieces generated.

448 pieces passed to the solution.
2)
    
"3"
Returns: 
"seed = 3<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/3_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/3_broken.png>"
S = 321

N = 56800

195 pieces generated.

174 pieces passed to the solution.
3)
    
"4"
Returns: 
"seed = 4<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/4_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/4_broken.png>"
S = 265

N = 21168

73 pieces generated.

61 pieces passed to the solution.
4)
    
"5"
Returns: 
"seed = 5<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/5_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/5_broken.png>"
S = 281

N = 15457

57 pieces generated.

47 pieces passed to the solution.
5)
    
"6"
Returns: 
"seed = 6<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/6_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/6_broken.png>"
S = 353

N = 106368

373 pieces generated.

312 pieces passed to the solution.
6)
    
"7"
Returns: 
"seed = 7<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/7_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/7_broken.png>"
S = 289

N = 83521

291 pieces generated.

258 pieces passed to the solution.
7)
    
"8"
Returns: 
"seed = 8<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/8_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/8_broken.png>"
S = 289

N = 66204

230 pieces generated.

198 pieces passed to the solution.
8)
    
"9"
Returns: 
"seed = 9<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/9_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/9_broken.png>"
S = 289

N = 38628

139 pieces generated.

125 pieces passed to the solution.
9)
    
"10"
Returns: 
"seed = 10<br><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/10_original.png><img src=http://www.topcoder.com/contest/problem/BrokenClayTile/10_broken.png>"
S = 257

N = 53505

184 pieces generated.

157 pieces passed to the solution.

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.

MaintainPlanes



Used in:


Used as:



Writer:


Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10704

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14175&pm=10704

Problem Statement

    

Introduction

Airlines have to perform routine maintenance on their fleets. However, they do not want this maintenance to interrupt their flight schedules. You work for AAFE (An Airline that Flies Everywhere) and have been tasked with scheduling the AAFE maintenance crew.



AAFE has N planes in its fleet. Every day, each plane flies a number of routes, ending the day at some location. As the airline flies everywhere, the planes end up scattered all over the world, sometimes even landing in the ocean or at the poles (the planes are all equipped for this).



The maintenance crew can service one plane per night, and getting to the correct location during the day is never a problem. However, they are paid per km traveled (in addition to a base salary and generous healthcare package) so AAFE would like for them to travel as little as possible. Furthermore, if they travel more than 4500km in one day, they will be paid double.

Problem

Your task is thus to determine a schedule for the maintenance crew under which the crew travels as little as possible. The crew will start at a home location (as specified by latitude and longitude) and must service one as-yet-unserviced plane per night for the next N nights. After the final plane has been serviced, the crew will return home for one night off before the next maintenance cycle begins. Night is used loosely in this context, as the crew will end up in many different timezones, and night refers to night UTC.

Implementation Details

You will be given an int N, indicating the number of planes, and an int M indicating the number of cycles. You will also be given the crew's home location as two doubles, start_lat and start_lng. The schedule for the N planes will be given to you as a single double[]. The simulation will have (N+1)*M nights for the M cycles of N planes plus one night off per cycle. The input will thus contain 2 * N * (N+1)*M elements. The ending latitude of plane j on night i of the simulation will be given by element 2 * (i * N + j) of the input. The longitude will be the next element: 2 * (i * N + j) + 1.



The planes are numbered 0..N-1. You should return a int[] with N*M elements indicating the planes to be served in each cycle. The first N elements of your return should be a permutation of the integers 0..N-1, as should the next N and so on.



For example, imagine that there are two planes and two maintenance cycles (N=M=2). The input might look like 
{
  10,   0,     40, -90, //ending locations for two planes on day 0
  20,   105,  -25,  43 //day 1
 -20,  -15,   -65, -143 //day 2
  50,  -45,   -35,  13 //day 3
  10,  -175 ,  15,  74 //day 4
 -5,   -85,    25,  18 //day 5
}
Imagine that the maintenance crew starts at 0,0. They need to service planes at the end of days 0,1, 3, and 4. If they service plane 0 on nights 0 and 4, and plane 1 on nights 1 and 3, then their route would be: 
0,0 -> 10,0 -> -25,43 -> 0,0 -> -35,13 -> 10,-175 -> 0,0
In this case, you would return {0,1,1,0}.

Scoring

The average cost, AVG, of travel by the crew is determined by the first finding the great circle distance (km) between consecutive points on the crew itinerary. Any of those that are 4500km or more will then be doubled. The average of these costs is then taken. Your score for each individual test case will be 10000/AVG. Your overall score will simply be the sum of your individual scores. If you fail a test case (your program doesn't return an answer, or your answer is invalid) you will receive a 0 for that test case.

Visualizer/Offline Tester

You may download a tool to aid your development at http://www.topcoder.com/contest/problem/MaintainPlanes/vis.html.

Environment & Target Configuration

NVIDIA Tesla C1060 with 4GB of Global Memory

Intel Q8200 CPU

4GB of system memory

Centos 5.3 Linux

NVIDIA GeForce GPU for graphics

Your application should use NVIDIA CUDA 2.3 SDK.

gcc, g++, CUDA 2.3 drivers, tookit and SDK are installed on the servers, and execution path and Library paths setup.
 

Definition

    
Class:MaintainPlanes
Method:schedule
Parameters:int, int, double, double, double[]
Returns:int[]
Method signature:int[] schedule(int M, int N, double home_lat, double home_lng, double[] positions)
(be sure your method is public)
    
 

Notes

-Latitude values will be between -90 and 90, inclusive.
-Longitude values will be between -180 and 180, inclusive
-The Earth is treated as a perfect sphere with radius 6378.1km.
-The distance between two points is calculated as the great circle distance
-Note that this problem uses degrees, not radians.
-There are 50 provisional tests.
-M and N are chosen uniformly. All of the landing points are chosen uniformly over the surface of the earth.
 

Constraints

-N will be between 30 and 100, inclusive.
-M will be between 5 and 30, inclusive.
-The time limit is 20 seconds per test case.
-The CPU memory limit is 1024MB.
 

Examples

0)
    
"1"
Returns: "seed = 1
<br>M = 5
<br>N = 30
<br>"
1)
    
"2"
Returns: "seed = 2
<br>M = 5
<br>N = 40
<br>"
2)
    
"3"
Returns: "seed = 3
<br>M = 11
<br>N = 81
<br>"
3)
    
"4"
Returns: "seed = 4
<br>M = 13
<br>N = 73
<br>"
4)
    
"5"
Returns: "seed = 5
<br>M = 28
<br>N = 86
<br>"
5)
    
"6"
Returns: "seed = 6
<br>M = 18
<br>N = 63
<br>"
6)
    
"7"
Returns: "seed = 7
<br>M = 23
<br>N = 64
<br>"
7)
    
"8"
Returns: "seed = 8
<br>M = 25
<br>N = 93
<br>"
8)
    
"9"
Returns: "seed = 9
<br>M = 30
<br>N = 96
<br>"
9)
    
"10"
Returns: "seed = 10
<br>M = 30
<br>N = 100
<br>"

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.

MountainRoad

Simple Math, Simple Search, Iteration



Used in:

SRM 449

Used as:

Division II Level One

Writer:

dzhulgakov

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10546

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13903&pm=10546

Problem Statement

    

Your friend is going to the mountains on vacation. He will climb up and down several mountains, and he has asked you to calculate his total walking distance.



To simplify this task, everything will be represented on a 2-dimensional cartesian plane. The ground is represented as the x-axis, and the mountains are represented as the union of several isosceles triangles. You are given int[]s start and finish. For each index i, construct an isosceles right triangle with its hypotenuse lying on the ground from point start[i] to point finish[i].

The mountains are guaranteed to form a single connected non-degenerate polygon, where the height is positive everywhere between the start and end points. The path your friend will walk is defined as the upper part of this mountain, shown in bold in the figure above. Return the length of this path.



 

Definition

    
Class:MountainRoad
Method:findDistance
Parameters:int[], int[]
Returns:double
Method signature:double findDistance(int[] start, int[] finish)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
-An isosceles right triangle is a triangle with angles 90, 45 and 45 degrees. The hypotenuse of such a triangle is the side opposite the 90 degree angle.
 

Constraints

-start will contain between 1 and 50 elements, inclusive.
-start and finish will contain the same number of elements.
-Each element of start and finish will be between -1000 and 1000, inclusive.
-For every i start[i] will be strictly less than finish[i].
-The union of the isosceles triangles described in start and finish will be a single connected nondegenerate polygon.
 

Examples

0)
    
{1}
{7}
Returns: 8.485281374238571
In this case there is only one mountain.
1)
    
{0,3,4}
{5,9,6}
Returns: 12.727922061357857
This situation with three mountains is shown in the figure above.
2)
    
{1,4,5,6,-10}
{101,102,101,100,99}
Returns: 158.39191898578665
3)
    
{-5,-3}
{-2,-2}
Returns: 4.242640687119286

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.

DoNotTurn

Graph Theory



Used in:

SRM 436

Used as:

Division I Level Two

Writer:

Gluk

Testers:

PabloGilberto , ivan_metelsky , ged , zhuzeyuan

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10337

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13698&pm=10337

Problem Statement

    There is a NxN maze where each cell contains either a wall or empty space. You are currently in the top-left cell at coordinates (0, 0) and your goal is to reach the bottom-right cell at coordinates (N-1, N-1) making as few turns as possible. You can choose any of the four cardinal directions as your starting direction. Then, from each cell, you can either move forward one cell in your current direction or turn left or right by 90 degrees. You can only walk into empty cells, not walls.

You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:

X[0] = X0 MOD P

X[i] = (X[i-1]*A+B) MOD P (note that X[i-1]*A+B may overflow a 32-bit integer)

Y[0] = Y0 MOD P

Y[i] = (Y[i-1]*C+D) MOD P (note that Y[i-1]*C+D may overflow a 32-bit integer)

Cell (x, y) of the maze contains a wall if and only if it is neither the top-left cell nor the bottom-right cell and there exists a value of i between 0 and M-1, inclusive, such that x=X[i] MOD N and y=Y[i] MOD N. Return the minimum number of turns you must make to reach the bottom-right cell of this maze, or return -1 if it is impossible.
 

Definition

    
Class:DoNotTurn
Method:minimumTurns
Parameters:int, int, int, int, int, int, int, int, int
Returns:int
Method signature:int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M)
(be sure your method is public)
    
 

Notes

-In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
-The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.
 

Constraints

-N will be between 2 and 500, inclusive.

-M will be between 0 and 1,000,000, inclusive.

-X0, Y0, A, B, C and D will each be between 0 and 1,000,000, inclusive.

-P will be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
2
0
0
1
0
0
1
10
2
Returns: 1
There are no walls, so you will have to make only one turn.
1)
    
3
0
1
1
1
1
0
3
3
Returns: -1

The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):

.#.
.#.
.#.

The target is unreachable.

2)
    
3
0
1
1
1
1
1
3
3
Returns: 3

The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):

.#.
..#
#..

There is only one possible path and it requires 3 turns.

3)
    
10
911111
845499
866249
688029
742197
312197
384409
40
Returns: 12

The maze and the optimal path in it are given below ('#' denotes a wall, '.' denotes an empty cell, the path is illustrated using 'p' characters):

pp##..#..#
#pp..###..
.#p#.....#
##p...#.#.
.#p.##.#..
##p##.#...
#pp####...
pp#.#...#.
p#pppp#...
ppp##ppppp
4)
    
5
23
2
3
35
5
7
9
3
Returns: 2

The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):

...#.
.....
...#.
.....
..#..
5)
    
2
0
0
0
0
0
0
1
0
Returns: 1

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.

GrilleReconstruction

Encryption/Compression



Used in:

MM 47

Used as:

Division I Level One

Writer:

Unknown

Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10276

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13680&pm=10276

Problem Statement

    Grille cipher is a technique for encrypting a message by writing its letters onto a sheet of paper through a pierced piece of paper called grille.

To encrypt a message, the grille is placed on a gridded (for convenience) sheet of paper. The letters of the message are written in the cells of the grid which are located under the holes of the grille in order from top to bottom, from left to right. If the length of the message is greater than the number of the holes of the grille, the grille is rotated, and the rest of the message is written in the same way in the cells which are still empty. Finally, the grille is removed, and the rest of the grid is filled with random letters to complicate breaking the cipher. The encrypted message can be decrypted by using the same grille and reading the characters visible through its holes in the same order.

You have intercepted a sheet of paper with a grid of letters on it which looks like it's a message encoded with a grille cipher. Your task is to construct a grille which decodes the grid into a message which makes as much sense as possible.

You will be given a String[] grid which represents an NxN grid of 'A'-'Z' characters. You must return a String[] which represents an NxN grille, with '.' denoting a hole in the grille and 'X' denoting unpierced paper. Your grille can have at most H holes in each row and each column.

The grille you return will be scored in the following way. First, the message is retrieved by concatenating the parts of it which are read by applying the grille straight, rotated 90, 180 and 270 degrees clockwise in order. For each grille position, the letters of the grid which are placed under the holes of the grille are read in rowwise order, the letters of one row being read from left to right. After that the message is partitioned into dictionary words and unused letters. The partition is scored as follows: each maximal contiguous sequence of dictionary words not separated with unused letters adds (number of characters in the sequence)1.1 to the score, and each unused letter subtracts 0.33 from the score. The score for a test case is the maximal score over all possible partitions. Your overall score will be the sum of your individual scores, divided by the greatest score achieved by anyone for that test case.

Test cases are generated by choosing grid size N randomly between 5 and 50 and filling an NxN grid with 'A'-'Z' letters. Each letter is chosen randomly accordingly to the distribution of letters in the words of the dictionary. H is chosen randomly between 1 and floor(N/3).

The visualizer is available.
 

Definition

    
Class:GrilleReconstruction
Method:bestGrille
Parameters:String[], int
Returns:String[]
Method signature:String[] bestGrille(String[] grid, int H)
(be sure your method is public)
    
 

Notes

-For more details on the test case generation and scoring implementation see the visualizer source.
-Any kind of invalid return results in a zero score for this test case.
-The memory limit is 1 GB and the time limit is 20 seconds (which includes only time spent in your code).
-The source code size limit is 300KB.
-There are 10 example test cases and 100 full submission test cases.
-You can get the dictionary at runtime by calling the library method Dictionary.getWords() that returns the list of words ordered alphabetically.
 

Examples

0)
    
"1"
Returns: "seed = 1
N = 5
GCNQE
XSRTR
EIWTI
RCOLV
NJLOU
H = 1
"
1)
    
"2"
Returns: 
"seed = 2
N = 22
ISDBOIIUMROASELAARTEPN
CINIRLUANGSAOMRATRREEK
SLASNTAFIROTIOZTBRREEN
TGUNSFIESEBNSISINANIAI
AORIINPTIZQOIMSAIUGORR
NMTRONSYEINIERSINAAKHI
ELIGTVDLIOSNHNRXSEAUPA
DIROSSTNJHSTAHLUNSURKE
AMHOTNKEAINEYSOAESNANN
EESZIONVAPTUSEGSNEOAOW
SIIICEALUCYHCEEUIDCOHB
MRATPMNGRESIFBCGCGUVPG
CTSUTATOETRNEHSOLPQESS
TMGUIOTACSSKFPPODSEDYZ
LDCDLPCNAUIEGNAGURNMGD
RAIROSBDPEPLELAEETSNHU
LMISUNYIGFTBBSPDHIERDS
UETRTSUECHCCEKNFBPTDBM
EUPERFCNCURAEETOTERTWE
RTSRDOASROIEYTTTKHLNGS
YARRLEAEIRYDRIEPIYUYAR
THHESMSLUEPRSKGYASAGGD
H = 5
"
2)
    
"3"
Returns: 
"seed = 3
N = 24
NNTDNOLSDATFFNRTCIICOIEN
OSEULAYSCPOESVENVIDSLOUR
OSSNEEPCVHRBTKOFTNMGFNOI
HOSGNJESNLNPGSMDSRAWIIEE
YITPHGAIMOEUPKREISGYASWJ
REAETRELEIOLQGITAIINIELM
YWONVKESHOTMRNGUSEOETKVI
LLAYTGGRATKSVEDEOECBMNDU
EBITVBCMSORUIEBNGTVRRNOE
OESAGAMINIIGINWSLTERISHU
TRYIRITCRLTIRIEGSESSTFPS
HLSSCAMAACIBWCEYEGTACTRP
SSCEMTISCRDOUARGGMSAPNUC
IEGRULGLILUOSQGEBRHBOTEK
DPARNAAKLIUEPRSRIGDRNASA
ONYRESKTAEEOXLOPRHIKMSIE
ISMXSADTRKFELRNUIEGTLMPM
SCCSRGAETASRAPBESBDOKKOI
AETRRICTNINNPUOITSCISNIN
LSLTNSCNLCTNUSENIYAOSNLE
PHASESUPSECNLDIOSENRSEEV
STTBUTAIILMISDIUTELEOELA
LIOLLREINMTTVLALSLSIEOSC
UOCBANREAELKBRTLEAISEWGT
H = 3
"
3)
    
"4"
Returns: 
"seed = 4
N = 26
ACOIISONSOPOEEBIESENESMRCC
NTSRPVKCGIMRRATEWLAEGOIOAL
LFINABSNMAASPILOCEIABLNGAE
OGIOBPRLNTUTYUSOLMOLEDLTPF
RAIESRDEPEXONFAASSLFEPREMG
EAFTGAMAYENFENHOITMETDFFEE
EIAIUCGRARDOUFSDECRIEETNGC
LSHEYGBAAMUGILIPIAEIPOOCSN
YONSSSARTDPZOESMHENSIVESER
USNSNNRENAGARUCSTUNEEWTCMR
TUAALEIPEINCCCTRAESEANIFRP
YSMTTAOETCRISEOGLRRNYSETRO
NLOSWECAODINUTTAEIETOSCRBS
NNATRSSCSUNERTRBNTERPUSKAA
EODEIIIDHSOSOSUIPIENDTNOZN
SSITNNTEUMTMEROIXGTLOPNILA
SENISLNLAIIITLUEAUTSOIYTIC
OICPOKNSRSHSESNSOTNRTRINPL
NORAGINULPLWIFDIRDDRTMUSRE
CARAIPECTHITEEFCTOEKNNSINW
AVRARIZRNSMAVOLENRUDMBLRDY
INSJIISHEBAIELIAHAHREIEHTN
SIRTLAEDNTHRTAENBMWIMNLRSK
EDTNINCLOTITUHOSNSEUAISRSA
SVNZIATTTTAEOEISDRIAERCRGR
EUETVNTSGDEETRORRRFAPAINRA
H = 8
"
4)
    
"5"
Returns: 
"seed = 5
N = 25
LADMATYRERTRIFGEMITRETCNL
IVYRSRESGEHSCOFESTDRNWFLC
DACEHCOOALPUSAURINSUNLOER
FIUTOOKEIIDRDIFRVSSPAEPLA
MCLEVUMDFLEEEVNNLABIFBISP
EAEUCDLATNNRGHNAIOLLVZUTS
EITOROTDLTSUANTTUFNDTAABE
KNDNETGBSENESOONBISRUIARI
DIELCBILPIEYTAOGUAELPSWSA
TRHNCSEENEPRATCCIMBISTOOL
IIRIKTIOTSHIHSACABUAATRWV
LLSTSDREASSUNCEEANGIISIAR
IFRLNANIREAZONFOANORSVLEM
EHUUELAIYEENDSASRGASGLONT
NNVKRTLYESIEESDEADTRRBCEL
NEAZIISDSLHANGRENOIPEUEFI
ASAASDLEEMALIOESIUNDALTSG
USUASCLETKTTHTODMECMGSEEB
OKSRHVMITIILCBTPRLCLNGLIL
CMECNNOKPEDAABNOSESUPLNIR
CEOPPTEDHPTARMNWTUMBOOSRS
YNDRPOIRTEAFPPAITLEJSSIIL
HHTTMGNICPTTGMLQEISISRCDA
SESCLESKGTHETALASIOTPIENL
NIWMANTUOLRTKVRRWOSEIAUAN
H = 1
"
5)
    
"6"
Returns: 
"seed = 6
N = 39
OTKEEPASEOSUATIMOPBRHIVITPPRLPTISTSCARL
REEALUAHEPENNSNTEHESRAAIGPISTEDSOIEIHYG
EIORNDULUEIILEOSLELEBNDORTPRLSCUSSSEGYT
RSSMLUEATHSSRDDAVMETOTSGPSEEZOLMIHSEOTE
IEOTOUOIHSNOBKORSRAIPLRSLIEPMNNLRORSIRO
GECPIDMHHKFELSELSERISATRCUENFSIEOARCAPR
LLSUTNNNANTANNPSKASTSSIPRYLTRSUVARAOCMA
OSSBPPEEAROIRLAUSDMAMILSEEEIEBOMTBLSDRI
RSCECRCONPNSETSPESLSTSOUYTHOEFREROSSTNA
RACIERROUTRTDRESCCNSHPFDAENYZDSETETOLIA
SGRMSBBUERDSIVTSOOECGHEDSNTENETUASEAEAA
WENDDEEYACLNSOTSEEDOPEMTSENBTGIILIEATEM
EESMUGSRIAANIAGHLIHOUTOTETETOERCLLISPNR
IRSCSIIPSPEVEEXISSDLEOGYTHETONRMSDTODSC
RIRIMRMNTMIACLNDHVRUSLISIEYSEEAELMIMSRB
CTELHCDOSFHMLTSENTORRSPMEISOEERUBALANTE
ESEHRFATHLLMUNEEDLONETSODENLPEEEILCLEEO
ESOEECPLPASNVPURLZRRYMESRPLAOPEORNRCUSS
IAILEEATSEIIIIIALSELXEAEANEOSFASHRIEIEU
NHASTIRHAIMBACATREIZSIACEPNSUSGGVSSAOEA
OLTRHDHMTPCSCCKHOMSALEAEIFODHOMOEUSERTT
CEEPINOAAIHRAOEISECGAIEAOPRSASSOERLEBEI
TDDONGUMEYELEEHUBHMLLUINLNBUNSINEPRHPSN
DSTNESBEEMOLSIUCZMTABRBLAAGUVUEPARLSPAA
DINTRDISVTLISSTAEOXRSITSTSTGVETEGEAYTHT
YVNLRSSUYPNENLOSALENIHOEEYFRBEIQLAARMSG
IIDRONANAHLDOISEGAKLEGOOHUNAIOWREGOLAVS
FTIECUUSINURMOCECEKYARBETROIMSNERLSOILS
ZTRUSOITGIISCUROEEASFKEERSNEIIISRSUCORG
CIIEITRLGIGLSUMOPSOPOETHPROLTPRTSEILEEU
AEMDIAFABPRDSUCSHBRTOLIMYMSLRECDSUSDFDA
VRHLNLDSSDENQTUEETOIIBIESRFIIAISMOCPPRE
DENSDRGUAFRRABRRRRPNJFSPIOLDTRLDOEOTNST
ONCEOGUACLIEGADMISNEYSLPEIEGBRIYFEEZSSE
LIDRCRBLNWLASAASCIQTNRNIWOTYROGTSACAASL
ETSSSANODTOETNPZRRUSGTAMRPNSAOSRTIEPERS
CEUSLPARDTRFNDCCCCICILROLALHYHNTVRTSBTM
ETRLAMDEBCEQTAWDLSRTMIEIWCNSOATFNPYNEHN
PPCCASDONCOODKPEAYIRSACELAAATDLBETHLIAR
H = 10
"
6)
    
"7"
Returns: 
"seed = 7
N = 19
NIVENSSNNYLSROBOUTN
RGIHBYMOICBOPNTUARO
RPOENYHEECSGEOLSEET
CTISMGSIBTNRFTUTSLN
SLAISNNLOIDNIBPTNHU
LSOTSODUHCISRCNUORE
DNSHSTAEMAOSNIANCOB
IGEELPROSOASOGSOUTS
SAARIAGHXHDESMDEODU
VSRELALPIRPEGMIYRSU
OAAMCEORTMFIEEUFETN
COMOVYRESEPFROEPEON
GZGUIENCIAKINAESENR
FSPABYNRTAFMTTPURTO
IOCLUEALYAENBLIEUEO
OHILSUNGLMCTTTEEGTP
OTIMESEFEIBUETUEOEE
TSEOTDANMOLEERUSGAR
RDNRPEIOYSISIEGIHNN
H = 1
"
7)
    
"8"
Returns: 
"seed = 8
N = 16
TEGCRTLSSHDSITER
TGASCNERPRAASORU
TAUASCNHMTIILLND
NEIUSMRTRLRVSSER
XRCEGTSMLDATRIIO
TIUSESOSCEVRDNOS
TRRLGLCRSEYNSAAB
CESPNCOMCREIAASS
EHATRICNCIITACUR
LNTITRTIIVSCRSOT
LCAEOHXRSAINVNBG
OCIINRSLOTEZTWEI
DRERASILWTDESCIL
DSECGESIMNUEALNG
DYTEYSUKCEEARPAS
LADSCCUPAEVGVHRN
H = 5
"
8)
    
"9"
Returns: 
"seed = 9
N = 45
EUTESDNTOOSWPIHMOORDASLTESSSKHTTIDCPNUIAMXOPL
SYOMIARZEASVIVVITAIUHECOOOCLAHAINONTAEIEWICTM
BOLOBRLALIRSDDSEOABIRPNNTSEBUKMPNDEENNACUHUYD
WEISMIHSVAEUSDISEEUDYRENDSIRNARTDTTRNGRASUAAP
ACLEOREEGDEASAYDTYSRRCONREBSHITRCDLHMOCEINOAY
MDLGSRESBEIOKCSTIEFNCFHCNNEISTAOEDOPAADUCRNBS
PAAOLANETRMLSRSEATOTOARBLOTPMEVSNLRTCTYRIIIEE
REPNYPSISEEBRCESSINNUIBEORLSITASSKCPLESAILIYS
SYNEOCLEPUMTSFAGSIEEDENRITINSAEAUASSTLXYSDRTL
RDSMSERTPDSMVSPECIONZTSOEIRTADISSIAEYUNHDMLQS
EACGUKCAIARAGIIRLARRSNTHMCATUPNUEESSLITEUIMHT
EENSIDEYSCGEIFRAIGIIPDSSNTAHRLAISDLTANDOLOUGH
EDLMIKCNRNCIEGCYBGAONBMATEUPNAESOLRPSNDOOTSEO
BITATTPEDNITEEMDPISYBEEUETTUOBSZSTSEREFGESNBT
YDDYNDRALRBLDSSELIEAIADCOLSILESYSRTTOTGENBRUP
ERRRSLINPEGSEMNAAHSOIIBDCUENLSRLOCDSNBLTOGCSF
LMOSEUEPAHJSOLETTSNLLOENONFENDDRAFETRYIARTTSI
EPINSTNRSSRMMBCLGEGTOMRNUELIANASVLAUTNBDHAEYO
ONDMYGSTCINRRSPOEDNXLUTACFHNNNFAIRREINSSAHSND
VSORRDCWLUTCRMEOCPUIEEETCNTIFDKSLSWGIVMIAGUAR
ILNGTSYOATACAAATESIOMOIEOOOCLYIIDTOOTTRVLAOET
MDDNEIOECZSLEIITSACOALEFCYYVITAPISECEYLIETRSU
OTTITLLNTMOABCIELSYENTASLZKNINUMGLTAAEDSIUENN
OBHOAIPILULSAMTBQDTDCOONOSREDINRFGAPAHIMLUOGH
MEMOIRTRURDTOSETPEOARGIGSDLLGEXIDOLNIVOTGTLTE
SMSUMDMCDLAPUCRLRHONEYEIDRMRRXBOERERSCDIPSONN
TOIIKMINOIACEEYRSHEIAREHIINOAFALOHREILETIALES
GVSYTTDEISNONOMFRPOKIIOAOSAOSITARVECIALLNEONS
PLNESBHENPRLGIFEEAPADSSIERSLNOSNYMASOILORYUAI
ADAIRHGOPZFEETNCISAIROTEFISIERIINNCOOYSHRNOIT
NELNGTAUGNIGCNDPSTIITMGTUENSRRSSCDCBAHIUIYARF
UOOTARCIINAUYCHLDSCEHBISCPCOITETSGBIEUSOINEDN
SELETCRNVLPEGCBAEAEHDESIRETYIISUTEIIOMRERAEET
DROOEPEOOLORMSYIROTEEZSLNICGEIUZBOIPEGMOESTAR
UEPORTOADNRNUICMENNGPPETCEYAIGNGYECPNTSPAHIAI
SWYDNTTRLRCINRSISRLSFTUSOVOOSTOOOFSSTEGAGRGOS
EETLUNRCPCRNRATSRRGILASICWIELSPGUEMIDRSCTSNTS
ENNBELTWTBERNHMKRSCRENLIKTNUSOTMMPIPALEINPRTG
NERLTOVNSLRBCEAMCSSIIIIDNHIPPNURUESSFLRRPILAF
CSPSDEHGSARCTSNAANJNOTIYAANMNSEENTCEMSATOFYNN
EANNEDEELIANLOTORCTHLIRUULOYTSSICDVMIOCSERCUS
PBOASCOLSAALOPNIOAOEEMHTNOVILOECMNOGSUUIRVCNN
TGTEREYIMLOSEFEEOPCTAMCEDHTSTOOIYGNGAHNRNAIEE
ICAIIAGISCRNISTMEIENERHWMHZETIEUCWUNTHSSUEBWE
OEARESOCSRITRGLLTPOSCAAASIHWPKNDUAANMIATISSUI
H = 10
"
9)
    
"10"
Returns: 
"seed = 10
N = 18
RACENGCYCOSHAMUINR
NLLUIGWLSEFABNICME
MEUSEAVHNEDGNEHLAE
IOILEIOPNXEAOCNAEL
NUGEMAESANUIBVVLGA
CMITOIEZRHIEOIEAIN
OETSALNFUTMBRURHER
CINALISNEEROLGGEUI
EOEEVHTDOLROOOWIEB
RDFSLELOOUPMODTGWI
ARMBROSISTSHTSMKOB
IISFTOOMHECCXYAWAS
NNNIEOUSNGOALERCKL
RSPATISOPIESTLAUNU
EIRENLLOEEKNAIQAEB
NYLSDNOBAFAISSHEND
NREUSSLKIOWMASEGOV
IVOPNTNEIAGPAFTRIS
H = 4
"

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.

RayTracer



Used in:


Used as:



Writer:


Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10043

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13636&pm=10043

Problem Statement

    Rendering a computer generated image is a huge research area, with many aspects. In this problem we will focus on one aspect of this problem: rendering glass objects. In particular, you will be given the locations of a number of glass ellipsoids and a number of light sources. Each light source will cast some amount of pure, single frequency light, uniformly in every direction.



Each of the ellipsoids will have an index of refraction of 2, which determines the way light interacts with it (we will assume an index of refraction of 1 for the air around the ellipsoids). To make things simpler, we will ignore the effects of polarization in this problem.



When a ray of light strikes the surface of an ellipsoid (either from within or without) some of the light is transmitted through the surface, and some is reflected off the surface. The angle of the reflected light ray is given by the law of reflection. The angle of the refracted light is given by Snell's law. To determine what fraction of the light is reflected and what fraction is transmitted, we use the Fresnel equations. Since we are ignoring polarization, we will always be using a reflection coefficient of R = (RS+RP)/2. It is important to note that in some cases we have total internal reflection.



Your task here is to render a scene from a camera at (500,500,500) pointed in the -z direction. The camera has a view angle of 90 degrees. The only object in the scene other than the glass ellipsoids is a square surface spanning from (0,0,0) to (1000,1000,0). Your should return a double[] with one million elements, representing a 1000x1000 image from the camera. Pixel (x,y) should give the intensity of a ray pointed from the camera to the point (x+0.5,y+0.5).



It is easiest to think about the rendering process in terms of a two-stage ray tracer. To do this, we first calculate the intensity of light at each location on the square surface. Once this is done, we then consider a ray leaving the camera, towards a part of the scene. If the ray from the camera strikes the square surface, our task is now easy, as we've already computed the intensity of the surface. If, however, it strikes an ellipsoid, we can use the same equations mentioned above to determine the fractional contribution from the part of the light that passes through the surface and the contribution of the reflected light. It is important to note that the lights do not have any impact in the second stage. A good way to think about it is that the lights serve to illuminate the square surface in stage one, are then turned off, and the camera is turned on, while the square surface remains illuminated.



You will be given a String[] ellipsoids, describing the location and size of each ellipsoid. Each element will be formatted as "CENTERx CENTERy CENTERz A B C", describing an ellipsoid ((x-CENTERx)/A)2 + ((y-CENTERy)/B)2 + ((z-CENTERz)/C)2 = 1. You will also be given a String, lights, each element of which is formatted as "X Y Z", describing a light.



Your task is to return a double[], where element x*1000+y is the intensity of light observed by the camera when looking towards (x+0.5,y+0.5) -- a raster image, in other words.



When comparing your image to the reference image, the first thing we will do is normalize the image so that the average intensity of the pixels in the image is 1.0. Once this is done, we will compute the error of each pixel as abs(sqrt(YOU)-sqrt(REFERENCE)). Your score for an image will be the sum of the errors for the pixels in the image, plus 5% per second of computation. Your overall score will be computed using relative scoring. If the best score for a particular scene is BEST, and you score YOU, your score for that scene will be BEST/YOU.



Getting Started

Writing a ray tracer is no easy task, so to help you get started, a C implementation of this problem is being provided (it is designed to work offline -- it is not a submission). It works by picking a random direction, and emitting a single ray of light from each of the light sources in that direction. When a ray of light hits a surface, two recursive calls are made, one for the ray passing through the surface (unless there is total internal refraction) and one for the ray of light reflected off the surface. The intensities of these rays are scaled appropriately. This is continued until the intensity of the light drops below a threshold, or a maximum recursive depth is reached, or the ray strikes the square surface. The total intensity of the rays striking the surface in each 1x1 grid cell is accumulated. After a large number of random rays are emitted, the second stage of the algorithm starts. A ray is directed from the camera to each of the locations, and again when it hits a surface two recursive calls are made. If the ray hits the surface, the intensity of the 1x1 grid cell it strikes is recorded.



You may freely discuss how this implementation works in the forums, so long as you do not suggest or discuss improvements.

Test generation

The tests are generated by first picking N and M, the number of ellipsoids and lights, respectively. N ellipsoids are then randomly placed, where each one is placed so that it does not intersect with any of the others. The M lights are then placed so that none of them are inside any of the ellipsoids. The centers of the ellipsoids are randomly chosen as points in the view area. The 3 size parameters are chosen between 10 and 100. The ellipsoids will not intersect the square surface. The lights are chosen to have z coordinate between 200 and 500. The generation code can be found at http://www.topcoder.com/contest/problem/RayTracer/Generate.java.
 

Definition

    
Class:RayTracer
Method:render
Parameters:String[], String[]
Returns:double[]
Method signature:double[] render(String[] ellipsoids, String[] lights)
(be sure your method is public)
    
 

Notes

-Because your return will be scaled to have an average intensity of 1, that absolute scale does not matter.
-The reference images are created using a ray tracer which is much slower than your must be.
-The time limit for each image is 10 seconds.
-The grayscale images are created using the square root of intensity, as this gives a better visual.
-The memory limit is 1024M and there is no code size limit.
-Higher quality reference images (with less aliasing) are currently rendering.
 

Constraints

-There will be between 1 and 5 light sources, inclusive.
-There will be between 1 and 50 ellipsoids, inclusive.
 

Examples

0)
    
"2"
Returns: ""
N = 24, M = 1
Ellipsoids:
355.555813 667.041444 173.665646 12.305219 59.773426 89.020176
826.230430 786.352404 150.223397 14.390755 35.383386 87.782143
667.237420 170.324162 95.791570 35.318688 41.790706 43.550781
134.303892 371.361721 96.783811 20.400289 83.147760 66.971261
580.305987 484.447065 342.258477 42.326733 94.695663 80.017503
272.862839 183.284452 14.055876 22.566264 87.920914 13.655857
822.929677 235.210618 115.579985 18.262342 77.433294 38.093873
458.266701 495.745137 366.237962 60.626334 26.718073 43.352804
685.127395 676.027574 177.854815 94.862104 57.212536 21.895791
681.967684 411.231269 216.969798 16.202888 40.278567 31.230602
481.035034 488.286671 120.259859 63.655532 21.929522 77.593592
344.712235 407.579651 70.955672 17.122807 45.058801 27.119990
359.845557 433.530841 274.638790 64.319746 15.355656 68.182344
381.913272 215.099990 55.524497 55.630294 87.246979 52.587848
257.785911 553.719018 202.131459 25.835228 68.281704 70.110868
389.763205 519.052216 101.655762 11.681565 62.716370 50.440170
526.929602 859.139435 49.095130 56.389011 32.295167 11.397487
535.251174 347.207111 220.840284 13.231640 14.118912 48.733043
861.159948 123.506746 85.335577 39.909114 35.518625 15.171137
706.882425 629.411002 227.718114 34.179730 80.676735 25.793894
161.997989 694.620740 37.929031 78.473802 72.692455 22.062109
708.412394 376.536393 124.861267 62.638587 97.600654 54.880680
479.748163 691.753296 148.119063 29.063361 67.992412 30.165112
251.657143 789.169595 149.174982 67.703422 52.195775 92.153442

Lights:
181.841542 297.082054 294.933768
View
1)
    
"4"
Returns: ""
N=6, M=3
Ellipsoids:
274.298630 451.915186 174.504464 99.559977 67.143985 49.245827
792.077207 500.152747 151.437317 54.847691 55.870127 79.265737
619.077040 377.084440 251.555469 40.869409 50.642001 99.374695
775.510023 779.047563 90.415982 70.380960 88.262998 35.532162
582.125738 578.508633 384.639409 18.763131 35.582797 99.597106
458.401622 771.053509 102.818638 66.235406 40.553860 39.183200

Lights:
47.340377 704.185886 251.283742
469.565552 251.474000 409.377205
965.463116 925.586822 456.465714
View
2)
    
"6"
Returns: ""
N=7, M=2
Ellipsoids:
224.866428 449.603111 66.799925 65.726356 40.032166 50.668248
786.364561 704.536483 130.557594 20.663274 32.896199 49.076420
692.116266 605.334890 157.284514 71.480039 50.007858 91.725226
287.814970 240.556180 108.152490 16.243843 23.554243 97.180589
573.029385 711.530000 191.149081 86.079627 59.523708 97.701784
97.956431 510.595167 39.414780 53.039000 70.650097 36.204342
652.252283 700.323831 21.621894 80.427172 92.571358 10.112650

Lights:
772.816207 990.001285 375.171825
496.699032 225.881903 478.338844
View
3)
    
"13"
Returns: ""
N=5, M=2
Ellipsoids:
660.867516 641.377803 105.174348 86.132563 73.329361 75.988720
772.370163 503.765845 181.557957 21.448964 16.640658 24.002753
448.605534 614.133479 222.152266 57.257763 89.429672 56.439502
626.665710 515.739938 285.761068 39.326060 23.289240 25.539689
481.660246 719.439216 115.189538 58.283953 81.716163 36.972316

Lights:
266.547712 109.840554 226.816396
171.813133 932.643882 317.062191
View
4)
    
"15"
Returns: ""
N=6, M=5
Ellipsoids:
266.142005 287.157418 111.859221 65.772292 97.444718 90.397655
339.370621 741.168010 122.901719 58.844121 80.370298 97.333088
289.046760 617.816390 48.671553 74.435493 33.711698 38.757165
758.976133 515.780078 26.035708 61.735676 78.876435 22.708943
432.048182 642.425819 329.459385 92.894829 27.923886 89.856122
706.945808 904.219301 63.900782 27.230466 23.890994 61.872470

Lights:
439.961939 403.037767 221.468091
636.454249 271.118454 271.040817
215.413045 93.747428 366.247561
680.478774 51.452164 239.571366
381.317388 91.936059 341.247081
View

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.

SpiralWalking

Simulation



Used in:

SRM 407

Used as:

Division II Level One

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9793

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12179&pm=9793

Problem Statement

    You are playing a game where you must traverse a rectangular grid of cells using a spiral path. The map is given in a String[] levelMap, where the j-th character of the i-th element is the number of points associated with the cell in row i, column j. Rows are numbered from top to bottom, starting at 0, and columns are numbered from left to right, starting at 0. All coordinates in this problem will be given as (row, column).

You start at cell (0,0), the top left corner of the grid. You are facing right. You move by repeating the following strategy until you have visited every single cell on the grid exactly once. If there is an adjacent cell in front of you that you haven't visited yet, move forward to that cell. Otherwise, if there are still unvisited cells on the grid, turn 90 degrees clockwise.

To calculate your final score, add up all the points for the cells that you visited, but don't include the cells in which you changed direction. The first and last cells in your path will always be included in your final score.

See examples for further clarification.
 

Definition

    
Class:SpiralWalking
Method:totalPoints
Parameters:String[]
Returns:int
Method signature:int totalPoints(String[] levelMap)
(be sure your method is public)
    
 

Constraints

-levelMap will contain between 2 and 50 elements, inclusive.

-All elements of levelMap will contain the same number of characters.

-Each element of levelMap will contain between 2 and 50 digits ('0'-'9'), inclusive.

 

Examples

0)
    
{"111",
 "111",
 "111"}
Returns: 5
This is the spiral path you must follow: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (1,1).
1)
    
{"101",
 "110"}
Returns: 3
The grid is not always a square.
2)
    
{"00",
 "10"}
Returns: 1
3)
    
{"86850",
 "76439",
 "15863",
 "24568",
 "45679",
 "71452",
 "05483"}
Returns: 142
The following image shows your path. The yellow cell is the last cell you visit. You receive points for all the cells except the red ones.

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.

JohnnysCannon

Math



Used in:

TC China 08 - 1E

Used as:

Division I Level One

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , Mike Mirzayanov , ivan_metelsky

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8704

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13677&pm=8704

Problem Statement

    

Johnny has recently constructed a cannon, and he wants to a hit a ground target that is distance units away. The cannon shoots bullets at velocity units per second. When a bullet is in the air, its flight follows the standard laws of physics. This means that if he shoots a bullet at angle alpha from the ground, it will travel a distance of



     ( 2 * velocity^2 * sin(alpha) * cos(alpha) ) / g ,



where g is the acceleration of gravity on Earth. In this problem, we will use 10 as the value of g.



The cannon can only be set at the angles given in the int[] angles (all angles are given in degrees). Johnny must pick the angle that will land the bullet as close as possible to the target. Return this closest possible distance between the landing point and the target as a double.

 

Definition

    
Class:JohnnysCannon
Method:getDistance
Parameters:int, int, int[]
Returns:double
Method signature:double getDistance(int velocity, int distance, int[] angles)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1e-9.
 

Constraints

-velocity will be between 1 and 1000, inclusive.
-distance will be between 0 and 100000, inclusive.
-angles will contain between 1 and 50 elements, inclusive.
-Each element of angles will be between 0 and 90, inclusive.
 

Examples

0)
    
5
40
{ 0, 45, 90 }
Returns: 37.5
Here we can choose 0, 45 or 90 degrees. The first and the last options are not very clever as we will shoot ourselves rather than hitting any target. So, the best possibility is 45 degrees.
1)
    
10
5
{ 23, 76, 33, 12, 45 }
Returns: 0.30528437214108894
Here are the distances the bullet will travel using the given angles:



     23 degrees: 7.193...

     76 degrees: 4.694...

     33 degrees: 9.135...

     12 degrees: 4.067...

     45 degrees: 10.0



We will be closest to hitting the target if we choose 76 degrees.
2)
    
100
15
{ 4, 55, 22, 13, 7, 88, 90 }
Returns: 14.999999999999877
3)
    
120
20367
{ 4, 55, 22, 13, 7, 88, 90 }
Returns: 19013.842626068294
4)
    
1000
10000
{ 45 }
Returns: 90000.0

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.

DegreesToRadians

Simple Math



Used in:

SRM 342

Used as:

Division II Level One

Writer:

Kawigi

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7410

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10666&pm=7410

Problem Statement

    

In some forms of geometry, like the kind used in geographical longitude/latitude measurements, angles are measured in base-60. The base unit is the degree. One degree contains 60 minutes, and one minute contains 60 seconds.

You will be given the measurement of an angle in degrees, minutes, and seconds. Return the given angle in radians. Note that n degrees is equal to n*PI/180 radians.

 

Definition

    
Class:DegreesToRadians
Method:convertToRadians
Parameters:int, int, int
Returns:double
Method signature:double convertToRadians(int degrees, int minutes, int seconds)
(be sure your method is public)
    
 

Notes

-The return value must have an absolute or relative error less than 1e-9.
 

Constraints

-degrees will be between 0 and 359, inclusive.
-minutes will be between 0 and 59, inclusive.
-seconds will be between 0 and 59, inclusive.
 

Examples

0)
    
0
0
0
Returns: 0.0
Zero is zero, in either measurement system.
1)
    
180
0
0
Returns: 3.141592653589793
180 degrees is PI radians.
2)
    
359
59
59
Returns: 6.283180459042776
This is as close to a full circle as it gets.
3)
    
23
30
5
Returns: 0.41017661490272295

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.

InscribedTriangles

Geometry



Used in:

SRM 326

Used as:

Division I Level Two

Writer:

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6730

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10006&pm=6730

Problem Statement

    

A triangle is "inscribed" in a circle if all 3 points of the triangle are on the edge of the circle. For this problem, our circle will be centered at the origin and have a radius of 5. Our goal is to find the largest triangle (by area) we can inscribe in this circle. Normally, this would be any equilateral triangle, but in this case we have the added restriction that each point of our triangle must be within one (or more) of the valid ranges of degrees. The degree ranges are given in thousandths of degrees in corresponding elements of angleFrom and angleTo. For each range, angleFrom will be less than or equal to angleTo and each will be between 0 and 360000. All ranges are inclusive; see the examples for clarification. Return the area of the largest inscribed triangle that can be made while following these restrictions. If no triangle can be made, return 0.

 

Definition

    
Class:InscribedTriangles
Method:findLargest
Parameters:int[], int[]
Returns:double
Method signature:double findLargest(int[] angleFrom, int[] angleTo)
(be sure your method is public)
    
 

Notes

-The ranges may overlap.
-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-angleFrom and angleTo will each contain between 1 and 30 elements, inclusive.
-angleFrom and angleTo will contain the same number of elements.
-Each element of angleFrom and angleTo will be between 0 and 360000, inclusive.
-Each element of angleFrom will be less than or equal to the corresponding element of angleTo.
 

Examples

0)
    
{0}
{360000}
Returns: 32.47595264191645
We can use any point we want on the circle - so we can draw an equilateral triangle (which will be the biggest we can ever draw).
1)
    
{15000,25000,100000,265000,330000}
{15000,25000,100000,265000,330000}
Returns: 27.433829549752186
In this case, each of our ranges are single points. The biggest triangle can be made by using the points at 15°, 100°, and 265°.
2)
    
{245900,246500,249900}
{245915,246611,252901}
Returns: 0.002789909594714814
We only have 3 small ranges, all near to each other - so our best triangle is still really small.
3)
    
{42}
{42}
Returns: 0.0
It's hard to draw a triangle with one point.

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.

RandomWalking

Graph Theory



Used in:

MM 1

Used as:

Division I Level One

Writer:

lars2520

Testers:

lbackstrom , tools

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6377

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10015&pm=6377

Problem Statement

    A random walk in a directed graph starts at some node in the graph and then follows one of that node's outgoing edges uniformly at random. The process is then repeated from the next node and so on. If a graph consists of a single strongly connected component, then a random walk will eventually visit every node in the graph. In this problem, your program will make a random walk of a graph. However, you will only be able to observe the in and out degrees of the vertices that you visit. Your task is to make as short a random walk as possible such that you have visited every node in the graph.



You should write two methods: init and walk. The init method will be called first with a single integer argument: the number of vertices in the graph. Subsequent calls will be made to the walk method and will give a sequences of in and out degree observations. Both of these methods should return an integer between 0 and one million, inclusive, indicating the number of steps your program wants to move at once. So, if you want to take 10 steps in the first iteration, your init method should return 10. Then, you will be given 10 degree observations in the next call to the walk method.



You are allowed to observe at most 10 sequences of degrees (walk will be called at most 10 times). Each time it will be given a int[] with 2 elements per observations. Element 2*i and 2*i+1 will given the in and out degrees of the ith observation, respectively. If you ever return 0, it will be assumed that you are done and want to make no further observations.



Scoring will be based on two factors: the number of nodes that you visit before quiting, and the total number of observations you make. In the best case, you will stop as soon as you hit the last unvisited node, in which case you will get 100 points. If you don't visit all the nodes, you will lose half your points for each unvisited nodes, so your score will be 100*0.5unvisited. If you visit all the nodes and make some additional observations, your score will be 100-(percent extra observations)/3 (with a minimum of 0). For example, if you visited all but 2 nodes, you would get 25 points. If you visisted the last node on observation 100, but you made a total of 130 observations, you would receive 90 points (having made 30% extra observations). Your total score will simply be the sum of your individual scores.



The graphs will be generated via a very simple model. First, the number of nodes will be selected between 10 and 100, inclusive, with size K chosen with probability proportional to 1/K. Then, a probability, p is chosen between 0 and 10/K. For each potential edge (u,v) (where u does not equal v), that edge is added with probability p. If the generated graph has a single strongly connected component, it is kept, otherwise, p and all the edges are regenerated (the size is kept), and the process is repeated until a graph with a single strong component is generated.
 

Definition

    
Class:RandomWalking
Method:init
Parameters:int
Returns:int
Method signature:int init(int nodes)
 
Method:walk
Parameters:int[]
Returns:int
Method signature:int walk(int[] seq)
(be sure your methods are public)
    
 

Notes

-You will have a total of 20 seconds execution time (not 20 seconds per sequence).
-The memory limit is 64 MB.
-There are 100 test cases.
-Graphs are given as adjacency lists. For instance, in example 0, there are edges from node 0 to nodes 1, 2 and 9.
-The return from the 10th call to walk is ignored (treated as if it is 0).
-The calls to walk form a single continuous random walk. In other words, concatenating all of the inputs to the walk methods gives a continuous walk.
 

Examples

0)
    
"1"
Returns: 
"0: 1 2 9 
1: 0 4 5 6 7 
2: 3 8 9 
3: 2 5 9 
4: 0 2 3 6 7 8 
5: 8 
6: 3 4 5 7 9 
7: 1 4 6 8 9 
8: 1 3 7 
9: 0 1 2 5 7 
"
1)
    
"2"
Returns: 
"0: 4 5 7 8 9 
1: 0 3 4 5 6 7 8 9 
2: 0 1 3 4 5 6 7 9 
3: 0 1 2 4 5 6 7 8 9 
4: 1 3 5 6 8 9 
5: 0 1 2 3 4 6 7 8 9 
6: 1 2 3 4 7 8 9 
7: 0 1 2 3 5 6 8 9 
8: 1 2 3 4 5 7 9 
9: 0 2 3 4 6 8 
"
2)
    
"50"
Returns: 
"0: 19 28 41 43 45 46 48 
1: 4 11 15 17 19 25 26 34 39 40 44 47 
2: 3 9 12 16 31 34 40 43 46 
3: 2 5 13 16 25 28 30 32 35 38 40 44 
4: 6 14 18 22 31 35 47 
5: 2 4 14 16 20 26 27 37 
6: 0 5 12 14 16 21 25 27 33 36 37 44 47 
7: 0 31 32 36 37 43 44 
8: 0 10 17 23 27 29 31 32 33 35 37 40 45 47 
9: 2 3 10 11 14 15 16 32 38 48 
10: 6 8 12 23 37 44 48 
11: 8 9 10 17 19 20 34 48 
12: 1 2 13 20 22 30 31 33 39 41 45 
13: 1 6 9 19 33 36 41 45 
14: 6 20 22 25 31 37 41 43 49 
15: 3 8 9 21 24 33 39 
16: 6 12 22 23 24 26 27 29 36 38 39 44 
17: 5 9 13 21 23 24 27 34 39 42 43 45 49 
18: 9 10 14 20 22 24 25 26 29 31 32 35 44 
19: 12 16 20 22 23 25 28 34 35 46 
20: 0 1 2 3 7 11 18 21 25 27 44 45 49 
21: 3 4 7 9 10 14 23 28 33 37 42 48 49 
22: 1 7 12 19 21 26 30 40 43 44 
23: 0 3 4 5 8 9 11 14 27 30 38 41 43 45 49 
24: 5 6 8 11 15 16 23 30 32 34 35 36 37 42 
25: 0 8 16 18 19 31 33 34 46 
26: 0 11 13 27 33 35 40 45 49 
27: 7 11 21 23 38 39 40 
28: 0 7 8 9 24 27 30 31 33 41 44 
29: 6 7 9 12 18 19 26 30 32 34 38 41 47 
30: 1 4 7 14 18 22 23 26 29 31 32 44 45 47 
31: 0 4 11 14 18 22 29 30 37 45 
32: 9 13 17 20 21 24 26 28 29 30 35 42 
33: 6 8 9 14 16 21 22 24 25 28 30 37 40 42 45 47 
34: 7 21 29 36 43 
35: 11 15 18 41 43 46 
36: 9 25 28 48 
37: 0 7 10 18 28 38 42 
38: 3 4 12 13 15 17 18 23 27 35 
39: 1 19 35 37 47 
40: 9 16 18 29 38 42 
41: 2 3 15 16 17 22 25 32 36 37 40 42 45 
42: 2 9 15 16 23 28 30 34 
43: 0 8 22 23 27 29 33 37 45 46 
44: 2 18 30 42 47 48 
45: 0 8 12 26 32 34 40 
46: 7 9 18 23 24 25 30 33 36 37 40 
47: 11 12 13 14 19 29 36 44 48 
48: 15 23 25 33 38 
49: 12 18 22 25 26 42 43 
"
3)
    
"100"
Returns: 
"0: 1 6 7 10 11 14 17 18 19 20 24 25 
1: 0 2 3 4 6 7 8 17 23 25 
2: 0 3 4 5 6 11 16 19 21 24 
3: 0 2 10 13 14 15 16 18 20 23 
4: 0 3 10 13 14 15 18 20 21 22 23 25 
5: 6 8 11 12 14 15 16 17 
6: 0 3 5 8 9 10 11 12 16 19 20 22 23 
7: 1 17 18 20 23 
8: 1 4 5 7 12 13 15 17 20 22 
9: 1 4 5 6 8 11 12 17 19 21 22 
10: 1 5 7 9 11 14 16 18 19 
11: 0 4 6 9 10 18 21 24 
12: 2 3 5 7 8 9 10 11 17 19 20 
13: 1 7 8 9 12 22 24 
14: 1 4 7 8 9 16 17 21 
15: 1 7 10 12 16 18 19 22 
16: 1 13 14 15 21 22 
17: 0 2 4 14 15 18 
18: 0 3 4 12 16 17 19 22 23 24 
19: 0 1 4 7 8 9 10 11 12 20 21 22 24 
20: 2 3 4 5 6 7 9 10 12 13 16 17 19 22 24 25 
21: 0 1 6 7 8 9 14 20 25 
22: 3 4 5 6 7 10 11 17 
23: 2 4 5 6 8 12 16 18 20 24 25 
24: 0 9 11 13 14 17 18 25 
25: 0 1 6 7 9 15 21 23 24 
"
4)
    
"73380160"
Returns: 
"0: 1 2 3 4 5 6 7 8 9 10 
1: 0 2 4 5 8 10 
2: 0 3 4 5 6 7 8 10 
3: 0 1 2 4 5 6 7 8 10 
4: 0 1 2 3 6 7 8 10 
5: 0 1 2 3 6 8 9 10 
6: 0 1 2 3 4 7 8 9 10 
7: 0 1 2 3 4 8 9 10 
8: 1 3 4 6 7 9 10 
9: 0 1 2 3 4 5 7 8 10 
10: 0 1 2 3 5 8 9 
"
5)
    
"499769812"
Returns: 
"0: 5 22 25 28 63 
1: 13 24 26 43 58 61 
2: 5 9 14 17 20 23 26 40 50 
3: 9 27 35 37 38 49 54 57 
4: 29 44 45 62 
5: 9 44 48 62 63 
6: 9 18 31 43 46 61 65 
7: 0 12 19 25 34 39 
8: 9 17 21 44 53 62 63 
9: 0 3 5 17 27 44 53 
10: 7 16 24 37 38 56 67 
11: 3 4 13 15 32 50 64 
12: 1 7 14 20 28 29 30 32 52 59 60 65 
13: 2 4 34 44 51 57 
14: 8 23 28 36 53 54 55 62 63 65 
15: 1 6 27 30 48 55 57 
16: 2 10 26 47 53 61 66 
17: 5 8 11 24 30 41 42 50 59 
18: 0 6 11 33 35 44 52 59 68 
19: 6 41 49 55 
20: 18 25 36 39 48 58 
21: 1 4 19 27 30 35 43 47 48 
22: 11 15 32 41 58 62 66 
23: 5 17 18 20 21 34 35 43 
24: 0 5 37 50 51 61 62 63 
25: 7 15 21 36 
26: 8 10 20 36 41 43 56 
27: 3 12 14 34 38 51 55 59 63 64 66 
28: 3 15 26 49 56 
29: 2 9 22 35 41 44 46 49 59 63 
30: 28 32 40 41 
31: 5 9 27 49 52 55 56 
32: 2 5 33 41 55 57 59 63 
33: 26 38 51 63 66 
34: 14 41 42 
35: 7 10 28 31 57 67 
36: 2 13 19 50 
37: 6 13 14 41 47 49 54 60 63 
38: 6 22 39 
39: 9 13 16 22 48 58 
40: 8 25 28 47 59 
41: 0 8 18 25 38 46 53 60 61 62 
42: 13 18 33 39 56 60 65 
43: 2 5 13 14 27 34 57 
44: 8 11 17 25 27 37 
45: 16 36 38 48 50 56 59 64 65 
46: 1 3 8 14 16 19 24 50 64 
47: 14 25 32 40 60 67 
48: 3 10 18 32 35 50 56 61 
49: 8 20 25 29 43 54 
50: 12 13 14 16 31 33 34 47 49 57 58 61 
51: 24 36 46 61 62 
52: 33 35 38 41 44 48 64 
53: 5 12 13 24 28 40 
54: 3 22 34 42 45 65 
55: 1 9 10 15 16 31 36 38 61 67 
56: 4 6 9 32 38 54 59 67 
57: 5 13 16 23 24 25 29 35 36 41 46 54 65 
58: 13 18 23 26 33 34 57 60 61 
59: 0 4 14 19 35 37 42 47 54 65 
60: 8 18 21 24 53 66 
61: 0 3 11 13 19 22 51 62 
62: 4 8 20 28 48 49 50 54 
63: 2 3 28 35 39 51 52 53 64 68 
64: 13 21 36 46 55 
65: 3 6 14 29 36 43 50 55 
66: 19 20 25 54 55 56 59 
67: 3 5 7 17 19 22 48 54 59 
68: 2 8 20 23 31 48 
"
6)
    
"78736497"
Returns: 
"0: 1 19 24 32 
1: 7 13 20 27 
2: 3 5 29 
3: 6 16 28 29 30 
4: 6 
5: 11 14 16 17 22 31 
6: 1 2 8 31 
7: 29 30 
8: 4 10 12 19 
9: 15 22 
10: 0 12 13 18 29 
11: 2 7 17 20 
12: 11 13 20 27 29 
13: 3 5 6 11 23 
14: 21 25 27 28 
15: 11 24 25 31 
16: 1 29 
17: 5 9 28 
18: 1 6 29 
19: 5 6 24 26 
20: 0 5 12 17 30 31 
21: 14 20 30 
22: 1 15 19 20 26 30 
23: 6 8 13 26 28 
24: 0 13 14 16 20 
25: 3 23 31 
26: 14 20 23 24 
27: 3 15 20 23 30 
28: 1 10 12 22 29 31 
29: 9 18 28 31 32 
30: 27 
31: 5 16 24 30 
32: 26 28 30 31 
"
7)
    
"880114950"
Returns: 
"0: 3 4 7 10 11 13 15 
1: 2 3 5 8 9 13 17 
2: 4 5 8 9 17 
3: 6 9 12 
4: 3 5 6 10 11 13 15 17 
5: 0 2 3 6 7 11 13 16 
6: 1 2 3 4 8 10 11 13 14 15 17 
7: 0 1 2 3 9 12 13 15 16 
8: 0 5 7 14 
9: 0 3 5 6 7 8 10 13 17 
10: 0 1 2 3 5 6 8 14 15 16 
11: 0 1 4 12 16 17 
12: 1 2 3 5 6 9 11 
13: 3 5 7 8 14 15 16 17 
14: 2 3 4 7 11 12 13 16 
15: 1 2 4 6 7 8 10 12 13 
16: 0 5 6 8 10 12 13 14 
17: 2 5 7 8 13 
"
8)
    
"347340626"
Returns: 
"0: 1 2 5 6 7 9 10 11 
1: 4 6 10 
2: 5 6 8 10 
3: 4 5 7 9 
4: 5 7 8 9 11 
5: 0 1 3 7 9 10 
6: 2 3 4 5 8 11 
7: 1 4 6 9 10 
8: 4 6 9 11 
9: 2 8 11 
10: 0 1 2 3 6 8 
11: 6 
"
9)
    
"866165179"
Returns: 
"0: 1 7 12 13 18 19 38 45 
1: 5 6 12 14 21 26 31 35 38 43 44 
2: 4 5 6 16 17 27 33 36 43 
3: 7 8 9 16 23 28 29 30 46 
4: 3 7 17 23 28 31 32 35 36 37 38 39 46 
5: 1 4 13 14 15 17 18 31 33 41 
6: 2 7 14 15 18 29 30 34 38 42 44 
7: 2 10 11 12 16 18 19 35 45 
8: 16 18 19 28 38 47 
9: 3 18 21 37 38 39 41 46 
10: 0 3 5 7 9 19 23 27 29 33 34 38 
11: 5 20 22 36 38 39 41 
12: 4 10 16 17 26 33 37 
13: 1 3 6 7 11 21 22 25 26 30 31 32 34 36 37 44 
14: 1 5 7 8 12 16 18 30 31 32 40 41 42 
15: 2 10 14 20 25 35 40 
16: 8 12 14 15 20 21 25 26 35 36 
17: 2 12 14 15 20 26 28 29 32 
18: 5 8 9 13 14 17 19 23 26 27 38 
19: 7 16 17 28 29 35 36 39 40 42 45 
20: 1 6 9 12 13 27 29 33 39 47 
21: 15 23 26 33 41 44 
22: 10 12 21 32 35 36 39 41 42 45 
23: 0 4 7 10 24 28 32 36 38 41 47 
24: 6 8 10 12 14 16 18 21 29 32 33 39 41 
25: 0 9 16 21 24 27 36 37 38 
26: 2 10 14 16 17 22 33 34 37 43 45 
27: 4 10 11 18 23 28 34 35 36 39 41 43 
28: 8 9 13 15 22 24 25 26 30 35 40 
29: 5 9 24 26 31 33 46 
30: 7 9 13 17 21 41 
31: 4 9 14 15 23 24 40 
32: 5 9 10 11 16 17 18 24 37 40 41 43 
33: 2 6 7 16 21 25 39 42 44 46 
34: 1 2 5 8 10 11 14 20 28 32 35 40 46 
35: 1 10 13 15 16 24 40 41 
36: 3 8 10 14 15 17 26 30 40 41 45 46 
37: 1 4 17 22 23 25 26 28 29 39 43 
38: 2 5 23 24 27 28 31 45 
39: 1 3 7 16 17 34 41 46 
40: 1 14 20 24 29 33 38 44 
41: 2 6 12 23 31 34 40 42 47 
42: 1 2 12 15 29 30 38 39 47 
43: 9 12 31 38 
44: 3 5 7 10 20 35 36 37 40 46 
45: 1 4 6 17 21 23 25 30 31 34 40 42 46 
46: 4 5 7 11 13 23 29 31 34 41 
47: 4 8 9 14 17 21 32 36 38 44 45 
"

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.

PolyMove

Dynamic Programming, Geometry



Used in:

SRM 304

Used as:

Division I Level One , Division II Level Three

Writer:

dgoodman

Testers:

PabloGilberto , vorthys , Olexiy , lovro

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6190

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9825&pm=6190

Problem Statement

    You are given the vertices of a convex polygon in clockwise order. As you traverse the boundary in the given order, your heading adjusts toward your right at each vertex by more than 0 but less than 180 degrees. As you complete the circuit by going from the last vertex to the first vertex and then heading toward the second vertex, your total heading adjustment has been 360 degrees.

We want to increase the size of the given convex polygon by picking some of its vertices and moving them. We are not allowed to choose vertices that are adjacent to each other, and we are not allowed to move a chosen vertex a distance of more than 1. Of course the boundary segments between a moved vertex and its fixed adjacent vertices also move -- we require that moving boundary segments never intersect any other boundary segments. This guarantees that we will end up with a polygon (possibly not convex) that has a well-defined interior and exterior.

Create a class PolyMove that contains a method addedArea that is given the sequence of vertices of a convex polygon in int[]s x and y. It returns the greatest increase in area that can be achieved by choosing and moving vertices. The coordinates of the i-th vertex are given by the i-th elements of x and y. There is a boundary segment between the last vertex and first vertex.

 

Definition

    
Class:PolyMove
Method:addedArea
Parameters:int[], int[]
Returns:double
Method signature:double addedArea(int[] x, int[] y)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
 

Constraints

-x and y will contain the same number of elements, a number between 3 and 50, inclusive.
-Each element of x and of y will be between -1000 and 1000, inclusive.
-The points corresponding to x and y will be distinct.
-The described polygon will be clockwise convex as specified above.
 

Examples

0)
    
{0,1,2}
{0,1,0}
Returns: 1.0
This is an isosceles triangle that has an area of 1. We can increase its area most by moving the middle point from (1,1) to the point (1,2). Now the triangle will have an area of 2, so the increase in area is 1.
1)
    
{0,1,1,0}
{1,1,0,0}
Returns: 1.4142135623730951
This polygon is a unit square. We can move (0,0) and (1,1), moving them each one unit along the 45 degree diagonal to (-1/sqrt(2),-1/sqrt(2)) and (1+sqrt(2),1+sqrt(2)) respectively. The new polygon is diamond shaped and has an area of 1 + sqrt(2), so its area has increased by sqrt(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)2010, TopCoder, Inc. All rights reserved.

BallBouncing

Simulation



Used in:

SRM 281

Used as:

Division I Level Two

Writer:

lovro

Testers:

PabloGilberto , brett1479 , Olexiy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5919

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8078&pm=5919

Problem Statement

    

A ball is moving diagonally on a rectangular board composed of unit squares in rows rows and columns columns. Each square is identified by its row and column number. The lowermost row is marked row 0 and the leftmost column is column 0.

The ball is initially located in the middle of a starting square given by two integers, startrow and startcol, and is moving diagonally up-right at an angle of 45 degrees. Whenever it reaches a wall, it bounces off it at a right angle (an angle of 90 degrees) and continues moving. If the ball runs into a corner, it bounces back in the opposite direction from which it came..

A number of holes have been drilled in the board and the ball will fall in upon reaching a square with a hole. Given the board size, starting location and locations of holes, return the number of times the ball will bounce off a wall before falling into a hole, or -1 if the ball will continue bouncing indefinitely.

 

Definition

    
Class:BallBouncing
Method:bounces
Parameters:int, int, int, int, String[]
Returns:int
Method signature:int bounces(int rows, int columns, int startrow, int startcol, String[] holes)
(be sure your method is public)
    
 

Notes

-Bouncing back from a corner counts as only one bounce.
 

Constraints

-rows and columns will be between 1 and 1000000, inclusive.
-startrow will be between 0 and rows-1, inclusive.
-startcol will be between 0 and columns-1, inclusive.
-holes will contain between 0 and 50 elements, inclusive.
-Each element of holes will be formatted as "row column" (quotes for clarity), where row and column will be integers with no leading zeros representing a square inside the board.
-There will be no holes at the starting position of the ball.
-No two holes will occupy the same position on the board.
 

Examples

0)
    
8
11
2
1
{ "1 5", "5 3", "4 4" }
Returns: 3
This example corresponds to the image in the problem statement.
1)
    
6
5
5
3
{ "1 3" }
Returns: 7
Bouncing back from a corner counts as only one bounce.
2)
    
6
7
4
4
{ }
Returns: -1
With no holes, the ball is bound to bounce around for quite a while.
3)
    
3
3
1
1
{ "2 2" }
Returns: 0
4)
    
6
6
0
5
{ "4 1", "3 2", "4 3", "2 1", "3 0", "5 2" }
Returns: -1
5)
    
1000000
999999
66246
84332
{ "854350 4982" }
Returns: 1662562
6)
    
5
7
3
4
{ "0 6", "2 3" }
Returns: 5
7)
    
1
5
0
1
{ "0 3" }
Returns: 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)2010, TopCoder, Inc. All rights reserved.

SlowDigitalClock

Recursion, Simple Search, Iteration, Simulation, String Parsing



Used in:

SRM 260

Used as:

Division I Level Two

Writer:

gepa

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4765

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7994&pm=4765

Problem Statement

    

We have a big digital wall clock, but while hanging it on the wall, we mounted it upside-down by mistake (i.e. the display was rotated 180 degrees). To make things worse, the clock has a complicated mechanism inside that makes it go slow when it is upside-down, needing secsPerMinute seconds to advance a minute instead of 60 seconds. Note that even at the moment we hang the clock on the wall, this is not necessarily set at the correct time. The clock itself only displays hours (from 00 to 23) and minutes (from 00 to 59), including any leading zeros.

You are given a String currentTime in the form "HH:MM", representing the actual (correct) time at which the clock is mounted on the wall, and a String clockTime also in the form "HH:MM", representing the time the clock is displaying when it is mounted on the wall (the time that we would see if the clock was mounted normally, not upside-down). Assume in both times that the seconds part is 0, i.e., the time just changed to currentTime and the clock just advanced to clockTime. You are to compute the first time after the clock is mounted on the wall that the clock shows the correct time (i.e., the display as shown now that the clock is mounted upside-down represents the correct time) and return this as a String in the form "HH:MM", including any leading zeros. If the clock never shows the correct time, return an empty String.

When the clock time is read upside-down, the digits 0, 1, 2, 5 and 8 are the same, 6 is shown as 9 and 9 is shown as 6. The digits 3, 4 and 7 do not show any meaningful digits when read upside-down.

 

Definition

    
Class:SlowDigitalClock
Method:firstCorrectTime
Parameters:String, String, int
Returns:String
Method signature:String firstCorrectTime(String currentTime, String clockTime, int secsPerMinute)
(be sure your method is public)
    
 

Notes

-You may assume that when the clock display is updated to the next minute, this update takes zero time.
 

Constraints

-currentTime and clockTime will have exactly 5 characters each, in the form "HH:MM". "HH" will be an integer between 00 and 23, inclusive (including any leading zeros), "MM" will be an integer between 00 and 59, inclusive (including any leading zeros).
-secsPerMinute will be between 61 and 1000, inclusive.
 

Examples

0)
    
"01:11"
"21:09"
61
Returns: "01:12"

At the beginning, the clock shows the upside-down time "60:12" (of course, this is not a valid time, so this can not be the correct time). After 61 seconds, the clock will advance to 21:10, which is read upside-down as: 01:12. Since the correct time at the beginning was 01:11:00, now (61 seconds later) the time is 01:12:01, so (ignoring the seconds) the clock shows the correct time "01:12".

The figure below shows the normal clock display when it shows 21:10.

The figure below shows the same display upside-down (now showing 01:12).

1)
    
"01:10"
"21:09"
61
Returns: "01:12"
In 120 seconds, the time is 01:12, but the clock still shows 21:10 (which upside-down reads 01:12).
2)
    
"12:50"
"05:21"
125
Returns: "12:50"
The clock already shows the correct time at the beginning (and this remains correct for the next 60 seconds), so currentTime is returned.
3)
    
"05:46"
"23:50"
240
Returns: "11:10"
Be careful when changing days (after 23:59 comes 00:00).
4)
    
"12:34"
"23:45"
197
Returns: "02:11"
The first time that the clock displays the correct time may occur after several days.
5)
    
"12:34"
"23:45"
300
Returns: ""
In this case, the clock never shows the correct time.
6)
    
"00:00"
"00:01"
86
Returns: "01:22"

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.

PackingShapes

Geometry



Used in:

SRM 270

Used as:

Division I Level Three

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4751

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8067&pm=4751

Problem Statement

    

Little Timmy has a rectangular frame and several shapes cut out from cardboard. He tries to fit each of the shapes into the frame (one shape at a time). Sometimes the piece fits easily, sometimes it is clear that the shape is too big to fit... and sometimes Timmy just doesn't know. Then he always comes to ask you for help.

You decided to write a program that will answer Timmy's questions.

You will be given the width and height of the frame and a String[] shapes describing Tommy's shapes. Each of the shapes is either a circle or a rectangle. Each element of shapes is of the one of the following forms:

  • "CIRCLE RADIUS", where RADIUS is the radius of the circle.
  • "RECTANGLE WIDTH LENGTH", where WIDTH and LENGTH are the dimensions of the rectangle.

Your method is supposed to return a String[] results, where the i-th element of results is "YES" or "NO", depending on whether the i-th shape fits into the empty frame.

 

Definition

    
Class:PackingShapes
Method:tryToFit
Parameters:int, int, String[]
Returns:String[]
Method signature:String[] tryToFit(int width, int height, String[] shapes)
(be sure your method is public)
    
 

Notes

-The shapes may be rotated arbitrarily.
-The shapes may touch the frame, and they may even have a common part of the boundary.
 

Constraints

-width and height are between 1 and 1000, inclusive.
-shapes contains between 1 and 50 elements, inclusive.
-Each element of shapes is of one of the following forms:
  • "CIRCLE RADIUS"
  • "RECTANGLE WIDTH LENGTH"
-All numbers in shapes are integers between 1 and 1000, inclusive, with no leading zeroes.
 

Examples

0)
    
100
100
{"RECTANGLE 3 3", 
 "RECTANGLE 3 230",
 "RECTANGLE 140 1"}
Returns: {"YES", "NO", "YES" }
The first rectangle clearly fits, but the second one clearly doesn't. The third one can be placed inside the frame after it is rotated 45 degrees.
1)
    
100
100
{"RECTANGLE 100 100",
 "CIRCLE 50"}
Returns: {"YES", "YES" }
Touching the frame is allowed.
2)
    
10
100
{"RECTANGLE 99 9",
 "CIRCLE 22"}
Returns: {"YES", "NO" }
The rectangle can be rotated, but the circle is too large.
3)
    
170
900
{"RECTANGLE 200 700",
 "RECTANGLE 3 910",
 "RECTANGLE 1000 7",
 "CIRCLE 5",
 "CIRCLE 50",
 "CIRCLE 500",
 "RECTANGLE 1000 99"}
Returns: {"NO", "YES", "NO", "YES", "YES", "NO", "NO" }

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.

ObjectPacking

Simple Math, Simple Search, Iteration



Used in:

SRM 253

Used as:

Division II Level One

Writer:

lars2520

Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4675

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7227&pm=4675

Problem Statement

    

Given a rectangular object and several boxes (in this problem, we ignore the height of the box, so a box only has two dimensions) of different sizes, you want to find the box with the smallest area which is large enough to contain the object. When putting the object in the box, it's sides must be parallel with the sides of the box. Thus, you may only rotate the object 0, 90, 180 or 270 degrees (although for obvious reasons you only need to consider rotating with 0 and 90 degrees).

Create a class ObjectPacking which contains the method smallBox which takes an int objWidth, an int objLength (the width and length of the object), a int[] boxWidth, a int[] boxLength (the width and length of the boxes) and returns an int, the area of the smallest box that can fit the object. Element i in boxWidth and boxLength correspond to box i. If no box is big enough to contain the object, return -1.

 

Definition

    
Class:ObjectPacking
Method:smallBox
Parameters:int, int, int[], int[]
Returns:int
Method signature:int smallBox(int objWidth, int objLength, int[] boxWidth, int[] boxLength)
(be sure your method is public)
    
 

Notes

-There doesn't have to be any gap between the sides of an object and the sides of the box. Thus, an object with width 5 and length 7 will fit in a box with width 7 and length 5.
-Return -1 if there is no box big enough to contain the object (see example 1).
 

Constraints

-objWidth will be between 1 and 1000, inclusive.
-objLength will be between 1 and 1000, inclusive.
-boxWidth will contain between 1 and 50 elements, inclusive.
-boxLength will contain between 1 and 50 elements, inclusive.
-boxWidth will contain the same number of elements as boxLength.
-Each element in boxWidth will be between 1 and 1000, inclusive.
-Each element in boxLength will be between 1 and 1000, inclusive.
 

Examples

0)
    
7
3
{3}
{7}
Returns: 21
By rotating the object 90 degrees we can precisely fit it into the only box in the list, so the method should return 21 (7*3).
1)
    
5
8
{6,9,3}
{7,4,5}
Returns: -1
The object can't fit in any of the boxes, no matter if we rotate it or not. The method should thus return -1.
2)
    
17
5
{19,10,12,40}
{12,20,15,5}
Returns: 200
The object will fit in box 0, 1 and 3. The area of box 1 and 3 are 200 while the area of box 0 is 228, so the method should return 200.
3)
    
20
44
{36,42,18,37,33,5,30,10,29,9,11,16,48,50,34,44,33,12,31,41}
{42,45,46,24,23,21,21,8,26,25,48,12,10,45,18,6,12,22,42,45}
Returns: 1845
4)
    
1
10
{9,1,10}
{10,6,4}
Returns: 40
5)
    
5
4
{2,3,3,3,3}
{2,7,7,4,2}
Returns: -1
6)
    
3
3
{2,3,3,3,2}
{3,1,3,3,2}
Returns: 9

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.

TriangleType

Simple Math



Used in:

SRM 247

Used as:

Division II Level One

Writer:

lars2520

Testers:



Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4610

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7222&pm=4610

Problem Statement

    In Euclidean Geometry, triangles can be categorized into one of three types based on their angle measures. A triangle is acute if all three angles are less than 90 degrees. A triangle is obtuse if one angle is greater than 90 degrees. Lastly, a triangle with one angle at exactly 90 degrees is a right triangle.



It could also be the case that three positive integers can not possibly form the side-lengths of a triangle. This happens when the length of one side is equal to or larger than the sum of the lengths of the other two sides, because it would not be possible to connect the end points of the three sides in such a way that a triangle was formed.



Write a method that takes as input three positive integer side-lengths of a triangle. Return "IMPOSSIBLE" if a triangle cannot be formed. Return "ACUTE" if the triangle is acute, "OBTUSE" if the triangle is obtuse, and "RIGHT" if the triangle is right.
 

Definition

    
Class:TriangleType
Method:type
Parameters:int, int, int
Returns:String
Method signature:String type(int a, int b, int c)
(be sure your method is public)
    
 

Notes

-For a triangle with side-lengths x, y, and z and x <= y <= z.

* The triangle is right if x*x + y*y = z*z.

* The triangle is obtuse if x*x + y*y < z*z.

* The triangle is acute if x*x + y*y > z*z.

* It is impossible to have x + y <= z.
 

Constraints

-a, b, and c are between 1 and 10,000, inclusive.
 

Examples

0)
    
3
4
5
Returns: "RIGHT"
1)
    
3
4
4
Returns: "ACUTE"
2)
    
3
4
6
Returns: "OBTUSE"
3)
    
7
4
3
Returns: "IMPOSSIBLE"

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.

PatternCutting

Geometry, Search



Used in:

SRM 241

Used as:

Division I Level Three

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4425

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7216&pm=4425

Problem Statement

    

You have a rectangular sheet of paper, from which you wish to cut a pattern. The pattern is a figure composed of unit squares. You wish to cut out as many instances of the pattern as possible from the sheet of paper. The pattern may be cut out exactly as is, or may be rotated 90 or 180 degrees (in either direction).

You are given ints height and width, describing the size of the sheet of paper, and a String[] pattern that defines the pattern you want to cut out. pattern is composed of 'X' characters and period ('.') characters, where 'X' is part of the pattern, and '.' is not. The following respresents the 7 valid patterns with 4 'X's (ignoring rotations of the same pattern):

{"XXXX"}

{"XXX",
 "X.."}

{"XXX",
 "..X"}

{"XXX",
 ".X."}

{"XX.",
 ".XX"}

{"X.",
 "XX",
 ".X"}

{"XX",
 "XX"}

So, for the T-shaped pattern, from a 4 x 5 sheet of paper, you could cut out the pattern four times. One way would be like this:

A.BBB
AA.BC
AD.CC
DDD.C

You are to return an int indicating the maximum number of times the given pattern can be cut from the sheet of paper.

 

Definition

    
Class:PatternCutting
Method:getMax
Parameters:int, int, String[]
Returns:int
Method signature:int getMax(int width, int height, String[] pattern)
(be sure your method is public)
    
 

Constraints

-height and width will be between 1 and 6, inclusive.
-pattern will contain between 1 and 6 elements, inclusive.
-Each element of pattern will contain between 1 and 6 characters, inclusive.
-Each element of pattern will contain the same number of characters.
-Each character of each element of pattern will be 'X' or '.'.
-The first character of the first element of pattern will be 'X'.
-Each block of the pattern will be connected (horizontally or vertically) to the rest of the pattern.
-The pattern will not contain any empty rows or columns (it will not be "padded").
 

Examples

0)
    
4
5
{"XXX",
 ".X."}
Returns: 4
As in the problem statement, you can cut out the T pattern four times.
1)
    
6
5
{"XX",
 "XX"}
Returns: 6
Although there are 30 unit squares in the paper and only four used by our pattern, we are going to waste at least 6 squares from which we cannot cut another pattern. We can cut out no more than 6 of the pattern.
2)
    
4
3
{"XXXXX",
 "XX..."}
Returns: 0
Here, our pattern is simply too large to cut from the paper, so we can't cut it out at all.
3)
    
6
6
{"XXX",
 "X.X",
 "XXX"}
Returns: 4

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.

HingedDoor

Simple Math, Simulation



Used in:

SRM 275

Used as:

Division II Level One

Writer:

NeverMore

Testers:

PabloGilberto , brett1479 , Olexiy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3531

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8072&pm=3531

Problem Statement

    We've all seen hinged doors before, perhaps in the entrance to a kitchen. Have a look at the figure below to make things clear. This particular hinged door works as follows: From "rest position" (the solid line below), the door is pushed at one end, and it swings out through an angle (in the image, this corresponds to "1st swing"). Then, when the door is released, it swings to the other side (this is shown in the image as "2nd swing"), but this time, the angle through which it swings is reduced to a known fraction of the previous angle. Then, the direction is reversed again and once more, the angle reduced by the same fraction. Once the angle drops to 5.0 degrees or below, the door doesn't swing any more, but rather, it returns to "rest position".







Create a class HingedDoor which contains a method numSwings. The method takes an int initialAngle and an int reduction as input and returns an int corresponding to the number of times the door will swing before coming to rest when initially displaced by initialAngle. Remember that each time the door will swing through an angle reduction times less than the angle it swung through the previous time.
 

Definition

    
Class:HingedDoor
Method:numSwings
Parameters:int, int
Returns:int
Method signature:int numSwings(int initialAngle, int reduction)
(be sure your method is public)
    
 

Constraints

-initialAngle will be between 0 and 90, inclusive.
-reduction will be between 2 and 10, inclusive.
 

Examples

0)
    
50
2
Returns: 4
In this example, the door begins with an initial angle of 50 degrees. Then, the door will swing through a reduced angle of (1/2)*(50) = 25 degrees on the first swing. At this point, the door will reverse direction, and swing through an angle of (1/2)*(25) = 12.5 degrees. Continuing in this way, the door will swing once more through (1/2)*(12.5) = 6.25 degrees, and then through (1/2)*(6.25) = 3.125 degrees. At this point, the door will come to rest. Therefore, the correct return value is 4, since the door took 4 swings before coming to rest.
1)
    
45
6
Returns: 2
2)
    
23
3
Returns: 2
3)
    
3
3
Returns: 0
Careful! The initial angle is already below 5 degrees, so the door won't swing at all, but rather, return to rest position immediately.
4)
    
73
5
Returns: 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)2010, TopCoder, Inc. All rights reserved.

Crossroads

Geometry, Greedy, Simple Math



Used in:

SRM 217

Used as:

Division II Level Three

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3042

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5863&pm=3042

Problem Statement

    You are watching a car race. Each car starts a different point on the x-axis, travels at the same speed, and starts at the same time. However, each car is travelling along a different road (which extends to infinity in one direction, and is stopped by the x-axis in the other direction), and each road has its own direction specified by an angle between 1 and 179, inclusive. An angle of 90 indicates that the road heads directly in the positive y direction, while an angle of 1 indicates that the road heads just a little bit north of the positive x direction. Note that cars never head in the negative y direction.







Sometimes, two or more roads intersect at some point. When this happens, the car that reaches the intersection first is able to block the intersection so that no other cars can pass through it. If two cars reach an intersection at the same time, the one with the lower index passes, while the other one is blocked.





In this picture, the cars following the red paths make it through all of the intersections, while the cars on the gray paths are blocked.

You will be given a int[] angles, where the ith element of angles is the angle between the x-axis and the road that the ith car drives on, in degrees. The order of the elements of angles corresponds to the order of the cars along the x-axis (no two cars start at the exact same location), with the first element of angles corresponding to the car with the leftmost starting position on the x-axis.



Your method should return a int[] containing the 0-based indices of all the cars that will pass all of the intersections along their roads. Your return should be sorted in ascending order.



Note that the exact locations of the cars along the x-axis do not matter. All that matters is their order, and the directions in which they head.
 

Definition

    
Class:Crossroads
Method:getOut
Parameters:int[]
Returns:int[]
Method signature:int[] getOut(int[] angles)
(be sure your method is public)
    
 

Constraints

-angles will contain between 1 and 50 elements, inclusive.
-Each elemtent of angles will be between 1 and 179, inclusive.
 

Examples

0)
    
{105, 75, 25, 120, 35, 75}
Returns: { 0,  1,  5 }
The example from the problem statement.



1)
    
{1, 1, 1, 1, 1, 1}
Returns: { 0,  1,  2,  3,  4,  5 }
No two cars' paths will ever intersect, so they all pass all intersections.
2)
    
{13}
Returns: { 0 }
Only one car.
3)
    
{90, 123, 1, 23, 132, 11, 28, 179, 179, 77, 113, 91}
Returns: { 0 }
The first car passes all intersections. The last car will be stopped by the first car. All other cars are between those two, and will be stopped by one of them.
4)
    
{179, 89, 90, 91, 1}
Returns: { 0,  2,  4 }
Neither the first nor the last car will intersect with any other car. Car 1 and car 3 will both be stopped by car 2.
5)
    
{89, 91}
Returns: { 0 }
Both cars reach the intersection at the same time, and hence only the first one passes.
6)
    
{140, 118, 54, 166, 151, 44, 90, 5, 14, 6,
 64, 129, 74, 33, 134, 25, 11, 95, 65, 145,
 29, 162, 24, 147, 45, 103, 63, 97, 120, 156,
 167, 170, 19, 28, 100, 144, 161, 13, 157, 148}
Returns: { 0,  1,  6 }

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.

BadMazeStrategy

Simulation



Used in:

TCO04 Round 1

Used as:

Division I Level One

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2971

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5878&pm=2971

Problem Statement

    You will be given a String[] maze containing blank spots ('.' characters), walls ('X' characters), your character (a single 'Y' character), and the destination (a single 'D' character). You have implemented the following naive maze traversal strategy:
  • 1) Initially, set the current direction to Right.
  • 2) If you are on the destination spot, exit this process.
  • 3a) If taking 1 step in the current direction will lead to a blank spot or the destination take the step.
  • 3b) If taking 1 step in the current direction will lead to a wall or will leave the bounds of the maze, change the current direction by turning 45 degrees clockwise. For example, if the current direction is set to Right then turning 45 degrees clockwise will set the current direction to Down-Right.
  • 4) Go to step 2.
Character 0 is the leftmost spot in any element of maze. Furthermore, element 0 is the highest element of maze. Return the number of steps required to reach the destination, or -1 if this will never occur. A step is counted when you physically change spots but not when you simply change direction.
 

Definition

    
Class:BadMazeStrategy
Method:numSteps
Parameters:String[]
Returns:int
Method signature:int numSteps(String[] maze)
(be sure your method is public)
    
 

Notes

-If your character is at (element E, character C) of maze, and the current direction is Down-Right, then taking one step would leave you at (element E+1, character C+1) of maze. The other diagonal directions are treated analogously.
-The following sequence of directions are formed by consecutively turning 45 degrees clockwise:

Right, Down-Right, Down, Down-Left, Left, Up-Left, Up, Up-Right, Right.
 

Constraints

-maze will contain between 1 and 50 elements inclusive.
-Each element of maze will contain between 1 and 50 characters inclusive.
-Each element of maze will contain the same number of characters.
-Each character in maze will be (quotes for clarity) '.', 'X', 'Y', or 'D'.
-maze will contain exactly one 'Y' and one 'D'.
 

Examples

0)
    
{"XXXXXXX"
,"X.....X"
,"X.....X"
,"XY...DX"
,"X.....X"
,"XXXXXXX"}
Returns: 4
After taking 4 steps to the right, we reach the destination.
1)
    
{"XXXXXXX"
,"XY....X"
,"X.....X"
,"X.....X"
,"X....DX"
,"XXXXXXX"}
Returns: 7
After taking 4 steps to the right, continuing would lead into a wall. After changing direction to Down-Right we are still facing a wall, so we change directions again. Now facing downward we take 3 more steps and reach the destination.
2)
    
{"XXXXXXX"
,"XY....X"
,"X.....X"
,"X..D..X"
,"X.....X"
,"XXXXXXX"}
Returns: -1
We keep running around the perimeter while the destination lies in the center.
3)
    
{"DY............."}
Returns: 27
Don't run off the maze.
4)
    
{"Y..X.............."
,"XXX.XXXXXXXXXXXX.X"
,".X.X.XX.......D..."
,".XX.XXX..........."}

Returns: 39

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.

Soma

Brute Force, Geometry



Used in:

SRM 198

Used as:

Division I Level Three

Writer:

Rustyoldman

Testers:

lbackstrom , brett1479 , schveiguy

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2824

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5073&pm=2824

Problem Statement

    

Soma is a three dimensional puzzle invented by Piet Hein. You have seven pieces which are formed by joining cubes at their faces. (They are all of the non-convex shapes that can be so formed with four or fewer cubes). Six of the pieces are formed from four cubes and one is formed by three cubes. There are 27 cubes total. The pieces can be described by the following arrays which show how high cubes are stacked in each grid cell, and are also shown in the picture below. 

1 1 1   1 1 1   0 1 1
1 0 0   0 1 0   1 1 0

1 1   0 2   2 0   1 2
1 0   1 1   1 1   0 1

The pieces can be translated and rotated into any orientation, to build larger shapes, but can not be reflected (as in a mirror) or disassembled. Pieces may touch, but not intersect. Each piece is used exactly once in a solution.

Given pattern (a shape composed of 27 cubes, not necessarily connected), try to arrange the seven soma pieces into the same shape as pattern. In other words, you are constructing pattern using the seven pieces. Return the number of distinct solutions for pattern.

What is meant by "distinct":

In a valid solution each cube in pattern will be occupied by a cube from exactly one of the seven pieces. You could assign a number between 1 and 7 inclusive to each pattern cube to indicate which piece occupies that pattern cube. Two solutions are distinct if this assignment is different at one or more pattern cubes. Thus removing a piece which has rotational symmetry, rotating it, and putting it back "in the same place" does not produce a new distinct solution. But a rearrangement of some or all of the pieces which is equivalent to rotating or reflecting the entire pattern (assuming pattern has such symmetry) is considered distinct by this definition. For example the pattern, "21112", can be constructed in exactly two distinct ways using the pieces "211" and "12". The distinct ways are "211"-"12" and "21"-"112".

The pattern will be specified in a String[] similar to the arrays showing the individual pieces above. Each character indicates how many cubes are stacked at that location, starting from a common plane at a height of zero.

For example: 

{"333",
 "333",
 "333"}

specifies a 3x3x3 cube which is possible to construct with the seven soma pieces in 11520 distinct (as defined above) ways, so return 11520.

 

Definition

    
Class:Soma
Method:letMeCountTheWays
Parameters:String[]
Returns:int
Method signature:int letMeCountTheWays(String[] pattern)
(be sure your method is public)
    
 

Notes

-If no rotational symmetries are involved, there are 24 possible orthogonal orientations resulting from rotations in three dimensions. Visualize the 3x2 "L" shaped piece (which has no rotational symmetry). The top (long end) of the "L" can point in six directions x,y,z,-x,-y,-z. For each of those, the short leg of the "L" can point in one of four directions. 6 x 4 = 24
-Each of the other six pieces does have some rotational symmetry, and thus fewer possible distinct orientations.
-The rotation of a point about a line passing through the origin can be calculated using a single, vector by matrix, multiplication: [x y z]*M=[rx ry rz] where M is a 3 by 3 matrix, [x y z] is the original point and [rx ry rz] is the rotated point.
-Vector by matrix multiplication is defined as: for(i) { r[i]=0 ; for(j) { r[i]+=p[j]*M[j][i] } } where p is the original point and r is the rotated point.
-The matrix for 90 degree rotation about the x axis is: {{1,0,0},{0,0,1},{0,-1,0}}
-The matrix for 90 degree rotation about the y axis is: {{0,0,-1},{0,1,0},{1,0,0}}
-The matrix for 90 degree rotation about the z axis is: {{0,1,0},{-1,0,0},{0,0,1}}
-The easiest way to generate all possible orthogonal orientations is to rotate about the x axis (0,90,180 or 270 degrees), then about the y axis (0,90,180 or 270 degrees) then about the z axis (0,90,180,270 degrees). That is 64 combinations of rotations (4x4x4). Try all 64 and throw away those that produce duplicate results.
-Sequences of rotations in three dimensions are non-commutative. The order in which you apply the rotations matters.
-There are 240 fundamental patterns to form the cube, proven by the great mathematician, Prof. John H. Conway. 240 x 24 rotations x 2 (for mirror reflection) = 11520. There are 96 ways to rotate individual pieces in each of the 11520 "distinct" ways. 11520 x 96 = 1105920 which is the "over a million ways to build a cube" number the manufacturer uses.
 

Constraints

-pattern will contain between 2 and 27 elements, inclusive.
-Each element of pattern will consist of between 2 and 27 characters, inclusive.
-Each element of pattern will have the same number of characters.
-Each character in each element of pattern will be a digit between '0' and '9' inclusive.
-The sum of all the digits in pattern will be exactly equal to 27.
 

Examples

0)
    
{"333",
 "333",
 "333"}
Returns: 11520
The cube.
1)
    
{"345",
 "234",
 "123"}
Returns: 2800
The crystal.
2)
    
{"3330000",
 "0033300",
 "0000333"}
Returns: 28
The wall.
3)
    
{"21111111",
 "21111111",
 "21111111"}
Returns: 0
The chase lounge, impossible.
4)
    
{"67",
 "77"}
Returns: 1520
The tower.
5)
    
{"010000000000000000000000000",
 "110000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000000",
 "000000000000000000000000022",
 "000000000000000000000000022",
 "000000000000000000000002222",
 "000000000000000000000002222"}
Returns: 76
Replication.
6)
    
{"11100110001",
 "01001100111",
 "00000000000",
 "20002012011",
 "11011001001"}
Returns: 1
Disjoint.
7)
    
{"121",
 "222",
 "121",
 "121",
 "333"}
Returns: 78
The monument.
8)
    
{"020",
 "010",
 "010",
 "020",
 "343",
 "353"}
Returns: 42
The gallows.

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.

TurfRoller

Geometry



Used in:

SRM 203

Used as:

Division I Level Three

Writer:

Eeyore

Testers:

lbackstrom , brett1479

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2247

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5849&pm=2247

Problem Statement

    

Warning: This problem statement contains images that may not be visible to plugin users. For best results, use the standard Arena editor.

Raccoons dug up your lawn during the spring, but now they've agreed to resurface it for a modest fee. They come equipped with a turf roller and a truckload of rectangular turf strips of fixed dimensions. We say that "length" is the measure of a turf strip's longer edges, while "breadth" is the measure of its shorter edges. Your lawn is also rectangular: from a bird's-eye view, what we call "width" is the distance from its left border to its right border, and "height" is the distance from bottom to top.

For aesthetic reasons, you demand that the turf be laid at a certain angle. This angle is between 0 and 90 degrees, inclusive, and is measured counterclockwise from the bottom border of your lawn. In other words, the raccoons will ensure that the longer edges of every turf strip are inclined at precisely this angle relative to the horizontal axis.

It may well happen that a single turf strip laid at the desired angle is not long enough to span your lawn. In such cases, the raccoons lay several turf strips end to end, precisely aligning the shorter edges of subsequent strips. At no time will turf strips overlap. Any scraps of turf that overhang the lawn's borders are immediately trimmed off and discarded. Once the raccoons have completed their labors, the entirety of your lawn will be covered with fresh turf.

You are given five integers that respectively state: the width of your lawn; the height of your lawn; the angle at which turf is to be laid; the length of each turf strip; and the breadth of each turf strip. Calculate the minimum number of turf strips that the raccoons must use in the course of resurfacing your lawn.

 

Definition

    
Class:TurfRoller
Method:stripNum
Parameters:int, int, int, int, int
Returns:int
Method signature:int stripNum(int lawnWidth, int lawnHeight, int stripAngle, int stripLength, int stripBreadth)
(be sure your method is public)
    
 

Notes

-Turf strips must always be laid lengthwise, as in the illustrations below. Breadthwise orientation is not permitted.
-Each turf strip must be laid at the specified angle, even if a different angle would allow the whole lawn to be covered with a single piece.
 

Constraints

-lawnWidth is between 1 and 100, inclusive
-lawnHeight is between 1 and 100, inclusive
-stripAngle is between 0 and 90, inclusive
-stripLength is between 1 and 100, inclusive
-stripBreadth is between 1 and 100, inclusive
-stripBreadth is less than or equal to stripLength
-If the angle is not 0 or 90, then the input is such that the final result will not be affected by small precision errors in your intermediate calculations. Specifically, the result would remain the same if both the length and width of the lawn were greater by 0.1 or less by 0.1 than they are in the input.
 

Examples

0)
    
60
90
39
60
25
Returns: 8


This diagram shows that the raccoons can resurface a lawn of width 60 and height 90 by laying as few as eight turf strips, each of length 60 and breadth 25, at an angle of 39 degrees.


1)
    
26
6
38
20
14
Returns: 2








In an optimal configuration, the upper edge of the top left turf strip doesn't necessarily intersect with the top left corner of the lawn.


2)
    
8
9
0
3
3
Returns: 9
Here, the strips are laid horizontally.
3)
    
6
4
45
10
10
Returns: 1
4)
    
2
3
45
2
1
Returns: 6
5)
    
70
70
45
76
24
Returns: 6
6)
    
100
100
45
2
1
Returns: 5112
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.  
					

				

			

						

				

					

						
FanFailure 

						
Greedy



						
Used in:
 SRM 195

						
Used as:
 Division I Level One
            , 
            Division II Level Two

						

						
Writer:
 schveiguy

						
Testers:
 lbackstrom


            , 
            brett1479

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=2235

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=5070&pm=2235

					

				

				

					

						
Problem Statement
    

In a robust computer system, one of the most important pieces is the cooling.  Without proper cooling, processors can heat up to over 400 degrees C.  The reliability of a system can be measured by determining how many fans can fail without risking the system processor.  Each fan can be assigned a value indicating how much capacity it has to cool the system, and we can define a minimum cooling capacity, which the sum of the fan capacities must exceed to properly cool the system.  We define a Failure Set as a set of fans which are not necessary to cool the system.  In other words, if the fans in a Failure Set break, the system can still be properly cooled by the remaining fans.  The count of a Failure Set is the number of fans in the set.





To measure the reliability, we will define two values, the Maximum Failure Set (MFS) and the Maximum Failure Count (MFC).  A MFS is a Failure Set of fans with the largest count possible.  A set of fans may have more than one MFS (see below).  A Failure Set is an MFS if and only if there are no Failure Sets with a higher count.  The MFC is the largest value such that all fan sets with count <= MFC are Failure Sets.  In other words, any set of fans of size MFC or less can fail, and the system will still be properly cooled by the remaining fans.





Consider the fan set with capacities 1, 2, 3, and a cooling requirement of 2.  Two MFSs with a count of 2 exist: fans 1 and 3, or fans 1 and 2.  However, the MFC is not 2 because fans 2 and 3 is not a Failure set (fan 1 could not cool the system properly by itself).  Thus, the MFC is 1, because if any single fan fails, the system can still be cooled.





You will be given a int[] capacities, which designates how many units of cooling each fan provides, and an int minCooling, which designates the minimum units of cooling required to cool the system.  Your method should return a int[], where the first value should be the number of fans in the Maximum Failure Set (MFS), and the second value should be the Maximum Failure Count (MFC).

 
Definition
    
Class:FanFailure
Method:getRange
Parameters:int[], int
Returns:int[]
Method signature:int[] getRange(int[] capacities, int minCooling)
(be sure your method is public)
    
 
Constraints
-capacities has between 1 and 50 elements, inclusive.
-each element of capacities is between 1 and 1000, inclusive.
-minCooling is between 1 and 50000, inclusive.
-The sum of all elements in capacities will be greater than or equal to minCooling.
 
Examples
0)
    
{1,2,3}
2
Returns: { 2,  1 }
Example from the problem statement.
1)
    
{8,5,6,7}
22
Returns: { 0,  0 }
No fans can fail in this system.
2)
    
{676, 11, 223, 413, 823, 122, 547, 187, 28}
1000
Returns: { 7,  2 }
If you eliminate fans with 676, 11, 413, 122, 547, 187, and 28, you are left with 223 + 823 = 1046 units of cooling, which is sufficient, yielding an MFS size of 7.  If you eliminate 676, 823, and 547, you are left with only 984 units of cooling.  All combinations of 2 or less fans breaking leaves sufficient cooling, so the MFC is 2.
3)
    
{955, 96, 161, 259, 642, 242, 772, 369, 311, 785,
 92, 991, 620, 394, 128, 774, 973, 94, 681, 771,
 916, 373, 523, 100, 220, 993, 472, 798, 132, 361,
 33, 362, 573, 624, 722, 520, 451, 231, 37, 921,
 408, 170, 303, 559, 866, 412, 339, 757, 822, 192}
3619
Returns: { 46,  30 }
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.  
					

				

			

						

				

					

						
ConvexPoly 

						
Brute Force, Geometry



						
Used in:
 TCCC '04 Semifinals 3

						
Used as:
 Division I Level Two

						

						
Writer:
 dgoodman

						
Testers:
 lbackstrom


            , 
            brett1479


            , 
            vorthys

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=2012

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=5078&pm=2012

					

				

				

					

						
Problem Statement
    Given a rectangular grid of squares, how many different convex polygons can be drawn
whose vertices are all points on the grid and whose sides are either
horizontal, vertical or (45 degree) diagonal?

 
We define the width of the given rectangular grid to be the number of intersection
points along one if its horizontals (including both the leftmost and rightmost
points). Similarly the height of the grid is the number of intersection points
along one of its verticals.  We want to count the number of different "grid polygons"
that could be formed. A grid polygon is a polygon with the following properties:
  1. 
    1) Each vertex is located at a grid intersection point
  2. 
    2) Each edge of the polygon is either vertical, horizontal, or at an angle of 45 degrees.
  3. 
    3) It is a proper polygon, with no edge touching or intersecting another edge (except that
adjacent edges touch at their common vertex). 
  4. 
    4) The polygon is convex: every straight line joining any two interior points of the polygon is entirely contained in the interior of the polygon.



Two grid polygons should be counted as different if their boundaries are not identical. If they are the same shape but in different locations they are different.  But placing an extra vertex in the middle of an edge does not change the boundary so it does not create a new grid polygon.


Create a class ConvexPoly that contains a method count that is given two
ints w, the grid width, and h, the grid height, and that returns the number
of grid polygons that could be formed.




 
Definition
    
Class:ConvexPoly
Method:count
Parameters:int, int
Returns:long
Method signature:long count(int w, int h)
(be sure your method is public)
    
 
Constraints
-w will be between 2 and 100 inclusive
-h will be between 2 and 100 inclusive
 
Examples
0)
    
3
2
Returns: 19

XXXXXXX    XXXXXXX    XXXXXXX    XXXXXXX
 X    X     X   X     X     X    X    X
  X   X      X X      X     X    X   X
.  XXXX    .  X  .    XXXXXXX    XXXX  .

XXXX  .    XXXX  .    XXXX  .    X  .  .    .  X  .
 X X       X  X       X X        XX           XX
  XX       X  X       XX         X X         X X
.  X  .    XXXX  .    X  .  .    XXXX  .    XXXX  .


.  XXXX    .  X  .    XXXX  .    XXXX  .    .  XXXX
  X   X      X X       X  X      X   X        X  X
 X    X     X   X       X  X     X    X      X  X
XXXXXXX    XXXXXXX    .  XXXX    XXXXXXX    XXXX  .

.  XXXX    .  XXXX    .  XXXX    .  X  .    .  .  X  
    X X       X  X       X X        XX           XX  
     XX       X  X       XX         X X         X X  
.  .  X    .  XXXX    .  X  .    .  XXXX    .  XXXX  




All 19 possible grid polygons are shown above, with the polygon sides 
shown with 'X' and unoccupied grid points with '.'



1)
    
2
2
Returns: 5
2)
    
100
100
Returns: 8658940474595
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.  
					

				

			

						

				

					

						
CombinationLock 

						
Math, Simulation



						
Used in:
 SRM 181

						
Used as:
 Division I Level One
            , 
            Division II Level Two

						

						
Writer:
 antimatter

						
Testers:
 lbackstrom


            , 
            schveiguy

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1945

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4725&pm=1945

					

				

				

					

						
Problem Statement
    
Combination locks are convenient, because of their design.  A combination lock consists of a small wheel to input the combination, and a latch to actually lock things together.  The wheel contains consecutive numbers equally spaced around its edge, starting from zero and increasing clockwise.  The outer casing of the lock has a small notch.  To open the lock, you must rotate the wheel and align the numbers on the wheel with the notch in a specific order.



TopLock, a small company manufacturing combination locks, has recently decided to change its lock setup to give more security than the competitors.  Many typical combination locks have a set of three numbers which you must input in order.  TopLock locks will have a variable combination length which will be no less than three. In addition, they will be changing the number of numbers on the wheel, which will be between 10 and 100, inclusive.



To open a lock, you must follow the algorithm outlined below:

  1. 1. Set the current rotation direction to counterclockwise, and set N to the number of numbers in the combination.
    2. 
    
  2. 2. Rotate the wheel N full turns in the current rotation direction, where a full turn is a 360 degree spin that leaves the notch pointing at the same number.
    3. 
    
  3. 3. Continue to rotate the wheel in the current rotation direction until the notch is pointing at the next number in the combination, which successfully inputs that number.  Note that by rotating the wheel counter-clockwise, the number that the notch points to will increase.
    4. 
    
  4. 4. If there are no more numbers to input, open the lock, you're finished! Otherwise, reverse the current rotation direction, decrease N by one, and go back to step 2.
    5. 






It is guaranteed that no two adjacent numbers in combo will be the same, so as to avoid ambiguity in step 3. Also, the starting position of the lock, start, will not be the same as the first number in combo.



Given a int[] combo, indicating the combination of the lock, an int size, the number of numbers on the wheel, and an int start, indicating the number that the notch starts off pointing at, your method should return a double indicating the total number of degrees turned to open the lock.



For example, if combo = {10,20,30}, size = 40, and start = 6, you would first rotate the wheel three times counterclockwise and then 4 units to the 10, for a total of 3 * 360 + 4 * (360 / 40) = 1116 degrees, and then you would rotate twice clockwise and 30 units to the 20, and then once counterclockwise and 10 units to the 30.  Your method would in this case return 1116 + 990 + 450 = 2556.
 
Definition
    
Class:CombinationLock
Method:degreesTurned
Parameters:int[], int, int
Returns:double
Method signature:double degreesTurned(int[] combo, int size, int start)
(be sure your method is public)
    
 
Notes
-The numbers on the combination wheel start at 0 and go to (size - 1), increasing clockwise.
-Double return values must be correct to within an absolute or relative difference of 1e-9.
 
Constraints
-combo will have between 3 and 50 elements, inclusive.
-Each element of combo will be between 0 and (size - 1), inclusive, and no two consecutive elements will be the same.
-size will be between 10 and 100, inclusive.
-start will be between 0 and (size - 1), inclusive, and will not be the same as the first element in combo (i.e., the one with index 0)
 
Examples
0)
    
{10,20,30}
40
6
Returns: 2556.0
Explained above.
1)
    
{0,50,99}
100
65
Returns: 2642.4
2)
    
{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9}
10
5
Returns: 79344.0
3)
    
{64,93,87,3,22,53,64,53,11,90,11,59,30,6,11,17,72,0,38,55}
97
26
Returns: 79166.59793814432
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.  
					

				

			

						

				

					

						
BitmapToGraph 

						
Simulation, String Parsing



						
Used in:
 TCO '03 Qual. Round 2

						
Used as:
 Division I Level Three

						

						
Writer:
 lars2520

						
Testers:
 brett1479


            , 
            schveiguy

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1882

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4701&pm=1882

					

				

				

					

						
Problem Statement
    Graphs are relatively common data structures in computer science.  To visualize a graph, we often display it as a bitmap like this one:








However, an image is not very easy to work with for most purposes.  It is usually much easier to perform common tasks (like finding a shortest path) if the graph is represented as a set of nodes and edges.  In this problem, you will be given a graph as a bitmap, and are to convert it to a set of nodes and edges.





You have some information about the bitmap to make this task easier.  First, you know that all nodes in the graph are represented by a single pixel of a certain color, which will be represented by an 'N' in the input.  Furthermore, each edge will be a single color, represented by an 'E' in the input.  The rest of the pixels will be represented by '.'s.  After examining the images, you've come up with the following sketch for an algorithm to find and follow edges:

  1. First, find an 'N' that is adjacent to an 'E' (either orthogonally, or diagonally).
    2. 

  2. Start following the edge in the same direction as you went to get from the 'N' to the 'E'.
    3. 

  3. Then, as long as the edge has not terminated at an 'N', follow the edge ('E' pixels) by either continuing in the same direction, or if you cannot continue straight, by turning 45 degrees and continuing.  You should always go straight when possible, but if you cannot go straight, you will be able to go either 45 degrees left, or 45 degrees right, though not both.  In other words, if you cannot go straight, it will be unambiguous which way to turn (this is ensured by the constraints).
    4. 

  4. If, at any point, there is an 'N' straight ahead, or there is not an edge straight ahead and there is an 'N' 45 degrees off from straight ahead, then the edge you are following terminates at that node.  Again, this will not be ambiguous, so if there is neither an 'E' nor an 'N' straight ahead, then exactly one of the pixels 45 degrees off from straight will be 'N' or 'E'.
    5. 



Your task is to write a method parse, which takes a String[], bitmap, each of whose elements represents a row in the bitmap, and returns a String[], each of whose elements represents a single node.  To do this, you should first number all of the nodes, starting with the most upper most nodes, and breaking ties by doing the left most first.  Your numbering should start at 0.  Then, the ith element of the return should be a comma delimited list of all the <edge>s coming out of the ith node.  Each <edge> should be formatted as <dest>:<length>, where <dest> is the number of the node to which this edge connects, and <length> is the number of 'E's in the edge.  The list of edges in each element should be sorted in ascending order by the index of the element they connect to.  Ties should be broken by sorting the edges in ascending order by length.
 
Definition
    
Class:BitmapToGraph
Method:parse
Parameters:String[]
Returns:String[]
Method signature:String[] parse(String[] bitmap)
(be sure your method is public)
    
 
Notes
-Only list individual loops (edges from a node to itself) once.  See example 4.
 
Constraints
-bitmap will contain between 1 and 50 elements, inclusive.
-Each element of bitmap will contain the same number of characters.
-Each element of bitmap will contain between 1 and 50 characters, inclusive.
-Each character of bitmap will be an 'E', an 'N', or a '.'.
-If you follow each edge as described in the problem statement, each edge will terminate at a node.
-There will not be two adjacent 'N's.
-All of the edges will be traversed in the same manner in both directions.  In other words, if there is an edge from node i to node j, there will also be an edge from node j to node i which uses all of the same pixels.
-There will be no ambiguity as to which way to go when a 45 turn must be made.
 
Examples
0)
    
   {"NEEE.....N",
    "....EEEEE.",
    ".........."}
Returns: { "1:8",  "0:8" }
The upper left 'N' is node 0, and the upper right 'N' is node 1.  There is an edge with 8 'E's connecting them, so element 0 of the return is "1:8" since the edge from 0 to 1 is of length 8.  Similarly, element 1 of the return is "0:8"
1)
    
    {"N.N",
     ".E.",
     "N.N"}
Returns: { "3:1",  "2:1",  "1:1",  "0:1" }
The numbers of the nodes are as follows:

    0.1
    ...
    2.3


Thus, 0 is connected to 3, and 1 is connected to 2.
2)
    
   {"N..N..N",
    ".E.E.E.",
    "..EEE..",
    "NEEEEEN",
    "..EEE..",
    ".E.E.E.",
    "N..N..N"}
Returns: { "7:5",  "6:5",  "5:5",  "4:5",  "3:5",  "2:5",  "1:5",  "0:5" }
3)
    
   {".NE....NE..N",
    "E..E...E.E..",
    "E..E...E.E.E",
    ".EE....NE..E"}

Returns: { "0:7",  "3:2,3:4",  "",  "1:2,1:4" }
Notice that the loop from node 0 to itself is only listed once.  Also note that when there are multiple edges from one node to another, they are sorted by length.  Finally, note that there may be edge pixels that are not part of any edge.
4)
    
{".EE....",
 "E..E...",
 "E..E...",
 "NEEEEE.",
 "...E..E",
 "...E..E",
 "...E..E",
 "....EE."}
Returns: { "0:20" }
5)
    
{".EE.",
 "N..N",
 ".EE."}
Returns: { "1:2,1:2",  "0:2,0:2" }
6)
    
   {"N..N.........",
    ".E.E.........",
    "..EE....EN...",
    "...E.N.E.....",
    "...NEEEEEN...",
    "...E.N.E.....",
    "..EE....EN...",
    ".E.E.........",
    "N..N........."}
Returns: 
{ "6:4",
 "4:3",
 "6:3",
 "6:1,7:3,8:4",
 "1:3,5:5,9:3",
 "4:5",
 "0:4,2:3,3:1",
 "3:3",
 "3:4",
 "4:3" }
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.  
					

				

			

						

				

					

						
Satellites 

						
Geometry



						
Used in:
 SRM 180

						
Used as:
 Division I Level Three

						

						
Writer:
 Eeyore

						
Testers:
 lbackstrom


            , 
            brett1479

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1812

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4720&pm=1812

					

				

				

					

						
Problem Statement
    



A government agency plans to establish a network of satellites to
monitor rocket launches worldwide. You have been asked to develop
a simulation that will help assess the coverage of a given satellite
configuration. Given a collection of satellite positions and a collection
of launch positions, you are to determine which rockets can be accurately
detected before they leave boost phase.




For the purpose of this simulation, the Earth is a sphere with a diameter
of 12800 kilometers. When a rocket is launched, it flies straight up from
the surface. All satellites operate at an altitude between 200 and 1200
kilometers, inclusive, and hold their position for the duration of the
simulation. A rocket can be accurately detected only if it is visible
to at least three satellites when its boosters are depleted at the
altitude of 400 kilometers. In order to preclude floating-point error,
the simulation will not include cases in which the line between
a satellite and a rocket at the 400-kilometer altitude passes within one
millimeter of the Earth.




The locations of the rocket launches are specified by a
String[], rockets, each element of which contains
exactly 19 characters. The first nine characters encode a fixed-point
number in the following manner: the first character is either plus
('+') or minus ('-'); the next four characters are the integer part of
the number, padded with zeros as necessary; the next character is the
decimal point ('.'); the final three characters are the zero-padded
fractional part of the number. This number gives the latitude of the
rocket launch. The tenth character of each element in rockets
is a space, and the last nine characters give the longitude of the
corresponding rocket in the same fixed-point format.




Latitudes range between -90.0 and 90.0 degrees, inclusive, while
longitudes range between -180.0 and 180.0 degrees, inclusive. The equator
is at latitude zero; the North Pole, at 90 degrees; the South Pole, at
-90 degrees. Longitude zero runs through the Greenwich Royal Observatory
in London. Positive longitudes are measured to the east of Greenwich,
negative ones to the west. Longitudes 180 and -180, which are one and
the same, lie on exactly the opposite end of the globe from longitude 
zero. If a rocket were launched from the Eiffel Tower, for example,
its location would be given as "+0048.867 +0002.267".




The locations of the satellites are described by another
String[], satellites, each element of which contains
exactly 29 characters. The first 19 characters encode the latitude
and longitude, just as for rocket launches, of the terrestrial point
closest to the satellite. The 20th character is a space, and the
last nine characters give the satellite's distance in kilometers from the
Earth's surface, again using the same fixed-point format. For example,
a satellite flying at an altitude of 550 kilometers over Mount Everest
would have the location "+0027.988 +0086.925 +0550.000".




You are to return a int[] containing the zero-based indices,
sorted by ascending value, of those rockets that can be detected at an
altitude of 400 kilometers by at least three satellites.


 
Definition
    
Class:Satellites
Method:detectable
Parameters:String[], String[]
Returns:int[]
Method signature:int[] detectable(String[] rockets, String[] satellites)
(be sure your method is public)
    
 
Notes
-This simulation ignores collisions. Several satellites or rockets, or both, may occupy the same point at the same time.
 
Constraints
-rockets contains between 1 and 50 elements, inclusive
-each element of rockets conforms to the format described above
-satellites contains between 1 and 50 elements, inclusive
-each element of satellites conforms to the format described above
-the input is such that no line of sight between a satellite and a rocket at the 400-kilometer altitude passes within one millimeter of the Earth
 
Examples
0)
    
{"+0000.000 -0000.000"}
{ "+0000.000 -0000.000 +0200.000",
  "+0000.000 -0000.000 +0400.000",
  "+0000.000 -0000.000 +1200.000"}
Returns: { 0 }
All satellites are at the same latitude and longitude as the rocket, so all can see it. Note that satellites do not block one another's lines of sight.
1)
    
{"-0050.000 +0045.000","+0040.000 -0135.000"}
{"+0090.000 +0000.000 +1200.000",
 "-0090.000 +0000.000 +1200.000",
 "+0000.000 +0000.000 +1200.000",
 "+0000.000 -0090.000 +1200.000",
 "+0000.000 +0180.000 +1200.000",
 "-0000.000 -0045.000 +1200.000",
 "-0000.000 -0135.000 +1000.000",
 "-0011.000 -0136.000 +1086.828"}
Returns: { 1 }
Satellites 0, 6, and 7 can see rocket 1, their lines of sight coming within about 59.593, 215.477, and 0.000177 kilometers of the Earth's surface, respectively.  Only satellite 1 can see rocket 0.
2)
    
{"+0037.431 -0143.361",
 "+0037.443 -0143.375",
 "+0037.413 -0143.364"}
{"+0037.470 -0143.316 +0513.143",
 "+0037.443 -0143.388 +0342.159",
 "+0037.434 -0143.361 +1034.123"}
Returns: { 0,  1,  2 }
All satellites and rockets are within a single degree of latitude and longitude of one another's locations; hence, all rockets are visible to all three satellites.
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.  
					

				

			

						

				

					

						
RoboCourier 

						
Search



						
Used in:
 SRM 150

						
Used as:
 Division I Level Three

						

						
Writer:
 vorthys

						
Testers:
 lbackstrom


            , 
            brett1479

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1749

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4555&pm=1749

					

				

				

					

						
Problem Statement
    

A robotic courier needs to deliver a package through a minefield, following a safe path discovered by
a robotic scout.  The scout's path is not necessarily as efficient as it could be.  For example, it might
loop back on itself.  The courier need not follow the path exactly, but can take shortcuts when it can do
so safely.  





Each robot can make only three kinds of moves, each represented by a single letter: it can go forward 1 meter ('F'), 
pivot right 60 degrees ('R'), or pivot left 60 degrees ('L').  Notice that the locations on which a robot can begin or
end a move form a hexagonal grid.  
The scout and courier begin in the same location, facing in the same direction.  The courier's goal is to reach the last
location visited by the scout as quickly as possible.  To travel safely, the courier must always stay in the wheel tracks 
of the scout.  That is, any forward movement made by the courier must be along a path segment traveled by the scout.  Pivoting
left or right is always safe.  Note that the courier is permitted to follow a path segment in either the same or the opposite
direction as the scout.  Similarly, the courier may be facing in any direction when it reaches its final destination--it need not
end up facing in same direction as the scout.





The courier requires 3 seconds to pivot left or right 60 degrees, and 4 seconds to move forward one meter.  However, because
of acceleration effects, the courier can move faster when it makes several consecutive forward moves.  The first and last moves 
in any such sequence take 4 seconds each, but intermediate moves in the sequence take 2 seconds each.  For example, it would
take the courier 20 seconds to travel 8 meters in a straight line: 4 seconds for the first meter, 4 seconds for the last
meter, and 12 seconds for the six meters in between.





For example, suppose the scout follows the path "FRRFLLFLLFRRFLF" (all quotes for clarity only).  Altogether, it visits six locations, which can be drawn as



    _
   /6\_
   \_/5\_
     \_/4\
     /2\_/
     \_/3\
     /1\_/
     \_/


It begins in hexagon 1, facing upward, and travels in order to hexagons 2, 3, and 4.  It then returns to hexagon 2 before continuing on to hexagons 5 and 6.  The courier could deliver the package in a minimum of 15 seconds, using the path "FFLF" which visits hexagons 1, 2, 5, and 6.



The scout's path will be given as a String[] path, rather than as a single String.  For example, 
the scout's path above might have been given as {"FRRFLLFLL", "FRRFLF"}.
Note that there is no significance to where the breaks fall between strings in path; it is best to think
of all the strings being concatenated together.  Given the path, you must calculate the minimum time needed for
the courier to deliver its package.




 
Definition
    
Class:RoboCourier
Method:timeToDeliver
Parameters:String[]
Returns:int
Method signature:int timeToDeliver(String[] path)
(be sure your method is public)
    
 
Constraints
-path contains between 1 and 10 elements, inclusive.
-Each element of path contains between 1 and 50 characters, inclusive.
-Each element of path contains only the characters 'F', 'L', and 'R'.
 
Examples
0)
    
{ "FRRFLLFLLFRRFLF" }
Returns: 15
The example above.
1)
    
{ "RFLLF" }
Returns: 17
Even though the ending location is one meter in front of the starting location, the courier
cannot simply go forward, because that would not be safe.  It must follow in the tracks of
the scout.
2)
    
{ "FLFRRFRFRRFLLFRRF" }
Returns: 0
Scout ends up at starting location.
3)
    
{ "FFFFFFFFFRRFFFFFFRRFFFFF",
  "FLLFFFFFFLLFFFFFFRRFFFF" }
Returns: 44
The shortest path is "FFFRFFFFFFRFFFF".
4)
    
{ "RFLLFLFLFRFRRFFFRFFRFFRRFLFFRLRRFFLFFLFLLFRFLFLRFF",
  "RFFLFLFFRFFLLFLLFRFRFLRLFLRRFLRFLFFLFFFLFLFFRLFRLF",
  "LLFLFLRLRRFLFLFRLFRF" }
Returns: 24
5)
    
{ "LLFLFRLRRLRFFLRRRRFFFLRFFRRRLLFLFLLRLRFFLFRRFFFLFL",
  "RLFFRRLRLRRFFFLLLRFRLLRFFLFRLFRRFRRRFRLRLRLFFLLFLF",
  "FRFLRFRRLLLRFFRRRLRFLFRRFLFFRLFLFLFRLLLLFRLLRFLLLF",
  "FFLFRFRRFLLFFLLLFFRLLFLRRFRLFFFRRFFFLLRFFLRFRRRLLR",
  "FFFRRLLFLLRLFRRLRLLFFFLFLRFFRLRLLFLRLFFLLFFLLFFFRR",
  "LRFRRFLRRLRRLRFFFLLLLRRLRFFLFRFFRLLRFLFRRFLFLFFLFR",
  "RFRRLRRFLFFFLLRFLFRRFRFLRLRLLLLFLFFFLFRLLRFRLFRLFR",
  "LLFLFRLFFFFFFFRRLRLRLLRFLRLRRRRRRRRLFLFLFLRFLFRLFF",
  "RLFRRLLRRRRFFFRRRLLLLRRLFFLLLLLRFFFFRFRRLRRRFFFLLF",
  "FFFFLRRLRFLLRRLRLRFRRRRLFLLRFLRRFFFRFRLFFRLLFFRRLL" }
Returns: 169
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.  
					

				

			

						

				

					

						
ConvexPolygon 

						
Geometry



						
Used in:
 SRM 166

						
Used as:
 Division II Level Three

						

						
Writer:
 dimkadimon

						
Testers:
 lbackstrom


            , 
            brett1479

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1660

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4635&pm=1660

					

				

				

					

						
Problem Statement
    
A convex polygon is a set of n vertices that are joined by n edges, such that no two edges intersect and all angles are less than 180 degrees. We can represent a polygon by listing all the vertices, starting at one vertex and following the edges until that vertex is reached again. Thus, element 0 in the array represents the first vertex. The first vertex is connected to the second vertex (element 1), the second vertex is connected to the third vertex (element 2) and so on. The last element represents the last vertex, which is connected to the first vertex.



Given the vertices of a polygon, where the x-coordinate of vertex i is element i of int[] x and its y-coordinate is element i of int[] y, return its exact area.
 
Definition
    
Class:ConvexPolygon
Method:findArea
Parameters:int[], int[]
Returns:double
Method signature:double findArea(int[] x, int[] y)
(be sure your method is public)
    
 
Notes
-As long as your return has relative or absolute error less than 1e-9, it will be judged correct.
 
Constraints
-x and y will have the same number of elements.
-x will have between 3 and 50 elements inclusive.
-y will have between 3 and 50 elements inclusive.
-each element in x will be between -10000 and 10000 inclusive.
-each element in y will be between -10000 and 10000 inclusive.
-the represented polygon will NOT intersect itself.
-the represented polygon will NOT have any angles equal to or greater than 180 degrees.
 
Examples
0)
    
{0,0,1}
{0,1,0}
Returns: 0.5
This polygon is a right triangle with two sides of length 1. Its exact area is 0.5.
1)
    
{-10000,-10000,10000,10000}
{10000,-10000,-10000,10000}
Returns: 4.0E8
This is a 20000 x 20000 square.
2)
    
{100,80,30,-30,-80,-100,-80,-30,30,80}
{0,58,95,95,58,0,-58,-95,-95,-58}
Returns: 29020.0
Regular decagon with radius 100 and centre at (0,0)
3)
    
{-1646,-9172,-9830,-9802,-9749,-9474,-8668,-6832,120,8380,9338,9307,8042}
{-9998,-8619,-7863,3976,4541,5975,8127,9500,9612,8734,5216,-9042,-9689}
Returns: 3.55115104E8
Random polygon.
4)
    
{-6010,-7937,-8782,-9506,-9654,-9852,-9854,-9998,-9999,-9996,-9901,-9811,
-9444,-8798,-8580,-2085,6842,8339,9827,9946,9993,9959,9940,9855,9657,
8504,8262,7552,6326,5537,4723}
{-9976,-9947,-9873,-9739,-9654,-8501,-8475,-5009,475,4926,7078,8673,9417,
9785,9820,9974,9986,9979,9862,9211,-5070,-6599,-7121,-8624,-8912,-9710,
-9766,-9863,-9914,-9941,-9962}
Returns: 3.939960635E8
Another random polygon.
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.  
					

				

			

						

				

					

						
Mirrors 

						
Geometry



						
Used in:
 TCI '02 Finals

						
Used as:
 Division I Level Three

						

						
Writer:
 lars2520

						
Testers:
 Logan


            , 
            zoidal


            , 
            alexcchan


            , 
            brett1479

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=1008

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4375&pm=1008

					

				

				

					

						
Problem Statement
    

A hall of mirrors is a large room with many mirrors throughout it.  When you
look at one of these mirrors, often you end up seeing an object that is far
away and has been reflected off many mirrors.  To aid in the design of halls of
mirrors, you are to write a class Mirrors with a method seen, which will tell
you what object is seen, given a particular configuration of mirrors and
objects, and the location and direction being looked.


Your method will take a String[], mirrors, another String[], objects, and a
int[], start.  Each element of mirrors will be formatted as "<x1> <y1> <x2>
<y2>", representing a mirror that starts at point (x1,y1) and ends at point
(x2,y2).  All mirrors are double sided.  objects, will repesent all of the
objects that are in the hall of mirrors and might be seen.  Each element of
objects will be formatted as "<name> <x> <y>", representing a circular object
named <name>, centered at point (x,y) and with radius 1.  


Finally, start will represent the location and direction that a person is
looking from.  The first element will be the x coordinate, the second element
will be the y coordinate, and the third element will be the heading that they
are looking in.  The heading will be in the range 0 to 359, representing the
number of degrees in a counter-clockwise direction, starting from straight right (positive x), that the person is looking.  Thus a heading of 0 means the person
is looking in the positive x direction, a heading of 90 indicates the positive
y direction, and a heading of 45 indicates that the person is looking half way
between the positive x and positive y directions.


Your method must determine what is seen when a person stands at the given
coordinates and looks in the given direction.  If the person sees himself,
return "me".  If the person doesn't see any object or himself, return "space".
Otherwise return the name of the object the person sees.

 
Definition
    
Class:Mirrors
Method:seen
Parameters:String[], String[], int[]
Returns:String
Method signature:String seen(String[] mirrors, String[] objects, int[] start)
(be sure your method is public)
    
 
Notes
-All mirrors are double sided, and should be treated as line segments.
-All objects, and the person, are perfect circles and have a radius of 1.
-A mirror reflects light such that the angle formed between the mirror and the incoming light is the same as the angle formed between the mirror and the outgoing light.  Thus the angle between the incoming and outgoing light is 180-2*(angle between mirror and light).
-If you look along a mirror, the mirror has no effect.  (see examples).
 
Constraints
-Each element of mirrors will be formatted exactly as "<x1> <y1> <x2> <y2>", with no extra spaces.
-Each element of objects will be formatted exactly as "<name> <x> <y>", with no extra spaces or leading 0's.
-mirrors will contain between 0 and 50 elements, inclusive.
-objects will contain between 0 and 50 elements, inclusive.
-start will contain exactly three elements, the first two representing x and y, respectively, and the third representing the heading the person is looking in.
-All coordinates will be integers in the range 0 to 1000, inclusive.
-The heading (3rd element of start) will be in the range 0 to 359, inclusive.
-No objects or mirrors will overlap other objects, mirrors, or the person (this includes touching at one point).
-No element of mirrors will represent a point. (x1==x2 and y1==y2)
-Each object will have a unique <name> other than "me" or "space".
-Each <name> will contain only lowercase characters.
-To avoid cumulative rounding errors, the object (or "me" or "space") seen will be seen in 50 mirrors or less.
-To avoid rounding errors, the object seen will be seen definatively.  This means that no objects will be barely seen, or almost seen, and there will never be any question about which mirror is seen.  This is ensured by checking that the path to the object seen does not pass within 0.001 of any other object, mirror, or the person.
-Each element of mirrors, and objects will contain between 1 and 50 characters, inclusive.
 
Examples
0)
    
{"0 0 100 100"}
{"a 15 10"}
{10,5,90}
Returns: "a"
The one mirror is at a 45 degree angle
1)
    
{"0 0 100 100"}
{"a 15 10"}
{10,5,180}
Returns: "space"
2)
    
{"0 0 100 100"}
{"a 15 10"}
{20,5,135}
Returns: "a"
3)
    
{"0 0 0 1000","1000 0 999 1000"}
{"a 500 152"}
{2,0,1}
Returns: "a"
4)
    
{"10 0 20 0"}
{"a 30 0"}
{0,0,0}
Returns: "a"
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.  
					

				

			

						

				

					

						
Travel 

						
Brute Force, Geometry, Graph Theory



						
Used in:
 TCI '02 Semifinals 3

						
Used as:
 Division I Level One

						

						
Writer:
 lars2520

						
Testers:
 alexcchan


            , 
            lbackstrom

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=996

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=4372&pm=996

					

				

				

					

						
Problem Statement
    

A traveling salesman has recently decided to go international and sell his
wares around the globe.  He has done in depth research and has come up with a
list of cities which he thinks will provide the best market for his goods.  In
planning his trip, the salesman wants to minimize the total distance he has to
travel because he does not particularly like traveling (which is unfortunate
for him, as he is a traveling salesman) and furthermore, he figures
the less distance he has to travel, the cheaper his trip will be.  However,
this salesman is not particularily good at math, and so you must write a
computer program to help him find his way in the least distance.


You will be given a set of cities defined by their longitudes and latitudes.
In addition, you will be given the radius of the planet that this traveling
salesman resides on.  Assume that there are direct flights, both ways, between
every pair of cities that the salesman wants to visit, and that the flights
follow the shortest path possible (over the surface of the planet).  In
addition, the first element of the input String[] will be the city in which the
salesman lives, and thus his trip must start and end at this city.


Each city is defined by two numbers, a latitude and a longitude.  The latitude
is the number of degrees above the equator, with 90 being the north pole, and
-90 being the south pole.  The longitude is the number of degrees east or west
of some arbitrary, predefined point.  Thus, 90 degrees east is one quarter of
the way around the globe in the eastern direction.


If the result is not an integer, round it to the nearest integer (.5 rounds up)

 
Definition
    
Class:Travel
Method:shortest
Parameters:String[], int
Returns:int
Method signature:int shortest(String[] cities, int radius)
(be sure your method is public)
    
 
Notes
-Assume the planet is a perfect sphere.
-To find the cartesion coordinates of a city, assuming the center of the planet is at (0,0,0), use the following formulas:

x = r*cos(latitude)*cos(longitude)

y = r*cos(latitude)*sin(longitude)

z = r*sin(latitude)
 
Constraints
-cities contains between 2 and 9 elements, inclusive.
-Each element of cities represents a unique point on the globe.
-Each element of cities is formatted as "<latitude> <longitude>" where <latitude> is an integer in the range -90 to 90, inclusive, and <longitude> is an integer in the range -180 to 180, inclusive.
-radius is an integer between 1 and 1,000, inclusive.
-to avoid rounding errors, the shortest path, prior to rounding, will not be within 0.001 of <x>+0.5 for any integer <x>.
 
Examples
0)
    
{"0 0","0 1"}
1000
Returns: 35
The two cities are located one degree apart at the same latitude
1)
    
{"0 0","0 1","0 -1","-1 0","1 0","-1 -1","1 1","1 -1","-1 1"}
1
Returns: 0
2)
    
{"40 -82","-27 -59","-40 48"
,"26 -12","-31 -37","-30 42"
,"-36 -23","-26 71","-19 83","8 63"}
698
Returns: 4505
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.  
					

				

			

						

				

					

						
LawnMower 

						
Brute Force, Graph Theory



						
Used in:
 TCO04 Round 3

						
Used as:
 Division I Level Three

						

						
Writer:
 dgoodman

						
Testers:
 PabloGilberto


            , 
            lbackstrom


            , 
            vorthys

						

						
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=926

						
Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=5880&pm=926

					

				

				

					

						
Problem Statement
    
I am considering buying a big new riding mower, 
but I need to figure out how much hand trimming I will need to do.  My lawn is a 
square n x n grid of cells. Each cell is either grass, or it is a bush. It
is not possible to drive the mower over a bush.  


The new mower occupies two adjacent cells. As it moves, the back end goes over 
the same cell that the front end previously occupied, and the front end can be
steered either 
to the next cell in the direction the mower is headed, or to one that is 
45 degrees to the left or right.The following diagrams give examples showing the possible 
cells (1, 2, or 3) 
that the front of the mower could be steered to given the location of the front(F) 
and back(B).  

   - 1 2             - - 1
   - F 3             B F 2
   B - -             - - 3




I will build a shed for the 
mower which will occupy two cells that are adjacent (either diagonally or orthogonally). 
The shed is really just a roof over a concrete floor, so it is open on all sides and
the mower can freely pass through the shed going any direction. I am willing to destroy bushes to
make room for the shed. Each time I mow I must return the mower to the shed facing the same way as
before 
I started mowing. 


I don't mind going over the same places more than once, 
but every cell containing grass that I can't mow will have to be trimmed by hand.
Create a class LawnMower that contains the method trimNeeded that takes the
width of 
my lawn, n, and int[]s row and col giving the locations of my bushes, and returns the 
number of cells of grass that I will have to trim by hand (with my shed built 
in the best location).


An element of row and the corresponding element of col give the location of a bush. 
A bush may be listed more than once -- the repetitions can be ignored. 



 
Definition
    
Class:LawnMower
Method:trimNeeded
Parameters:int, int[], int[]
Returns:int
Method signature:int trimNeeded(int n, int[] row, int[] col)
(be sure your method is public)
    
 
Constraints
-n is between 2 and 12 inclusive.
-row contains between 1 and 50 elements inclusive.
-col contains the same number of elements as does row.
-Each element of row is between 0 and n-1 inclusive.
-Each element of col is between 0 and n-1 inclusive.
 
Examples
0)
    
4
{0,1,0}
{0,2,0}
Returns: 6
   B S S -
   o - B o
   o - - o
   - o o -


The best place (there are other equally good places) for the shed is row 0, 
columns 1 and 2. The mower 
can just barely mow in a circle and get back to the shed. Each 'o' shows 
a cell that the lawn mower cuts. Note that there are only two bushes (one is 
repeated). Each '-' shows a grass cell that cannot be mowed. 
1)
    
5
{0}
{0}
Returns: 4
With no bushes in the way (we can't get the mower into the corner anyway) and a 
bigger yard, we can build the shed at row 0, columns 1 and 2, and cut everything 
except the 4 corners and the middle. Since one of those corners has a bush, that leaves 4 grass cells that must be trimmed by hand.
2)
    
5
{3,3,3}
{4,4,4}
Returns: 5
There is just one (repeated) bush. We can build the shed on top of the bush 
at rows 3 and 4, column 4.
We will then be able to mow everything except the four corners and the middle.
3)
    
3
{0}
{0}
Returns: 6
This yard is just too small for the mower. We can build the shed on two grass 
cells and just leave the mower in the shed; that leaves the 9 cells containing 1 bush, 2 shed, and 6 grass, all of which must be trimmed by hand.
4)
    
12
{11}
{11}
Returns: 3
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.  
					

				

			

			1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 
Nikolay.IT 2009-2012