Jolly Jumpers..~

less..

Problem Statement
     
Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' (zero) or '.' he will construct donuts from the cells.
To make the donuts:
Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.
An example of large donut containing a smaller donut.
..........
.00000000.
.0......0.
.0.0000.0.
.0.0..0.0.
.0.0..0.0.
.0.0000.0.
.0......0.
.00000000.
..........
Donuts may contain other donuts and donuts may touch, but the cells of one donut may not overlap the cells of another. Petra is most interested in donuts that contain other donuts. He first places one valid donut on the grid (if possible). He then places a valid donut in the hole of the first donut (if possible). He continues to place a donut into the hole of the most recently placed donut until this is no longer possible.
Your task is to find the maximum number of donuts that Petya can place on the grid as described such that each donut (except for the first) is contained within the previous donut. You are given grid, a String[], containing only '0' and '.' characters. The j-th character of the i-th element is the value at cell (i, j).
Definition
   
Class:
DonutsOnTheGridEasy
Method:
calc
Parameters:
vector <string>
Returns:
int
Method signature:
int calc(vector <string> grid)
(be sure your method is public)
   
 
Constraints
-
grid will have between 1 and 50 elements, inclusive.
-
Each element of grid will have between 1 and 50 characters, inclusive.
-
All elements of grid will have the same length.
-
Each character of grid will be either '0' (zero) or '.'.
Examples
0)
 
   
{"0000000"
,"0.....0"
,"0.00000"
,"0.0..00"
,"0.00000"
,"0.....0"
,"0000000"}
Returns: 2
 
1)
 
   
{"000"
,"0.0"
,"000"}
Returns: 1
 
2)
 
   
{"..."
,"..."
,"..."}
Returns: 0
 
3)
 
   
{"00.000"
,"00.000"
,"0.00.0"
,"000.00"}
Returns: 0
 
4)
 
   
{"0000000....",
 "0000000....",
 "0000000.000",
 "0000000.0.0",
 "0000000.000",
 "0000000....",
 "0000000...."}
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)2003, TopCoder, Inc. All rights reserved.

less..

less..

Problem Statement
     
Petya likes triangles. He draws a trianglar grid using the following process: He starts off with an equilateral triangle. He then draws points on the edges of this triangle, dividing each edge up into N equal-length segments. Next, he connects each pair of points that is at equal distance from some vertex of the triangle with a straight line, ending up with N*N smaller equilateral triangles. An example of this figure with N = 4 is shown below.

 
However, he likes hexagons more than he likes triangles. How many non-degenerate convex hexagons can be formed using the line segments in his figure? This number can be very big, so return it modulo 1000000007.
Definition
   
Class:
ConvexHexagons
Method:
find
Parameters:
int
Returns:
int
Method signature:
int find(int N)
(be sure your method is public)
   
 
Notes
-
The length of each edge of every hexagon must be greater than zero.
Constraints
-
N will be between 1 and 500000, inclusive.
Examples
0)
 
   
4
Returns: 7
There are 7 hexagons: 


 
1)
 
   
7
Returns: 232
 
2)
 
   
104
Returns: 635471838
 
3)
 
   
1
Returns: 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)2003, TopCoder, Inc. All rights reserved.

less..

접기

Problem Statement
     
Petya likes oriented graphs, especially rooted trees. He has such a tree described in a string target. Every edge may be in an active or inactive state. Initially every edge is in an inactive state. Petya wants to change the states of all the edges so that they are all active. To do so he has some trees described in a vector <string> trees in which each element describes a single tree. Initially, every edge in target is inactive and he must activate them by repeating the following process:
 
He chooses some vertex V from target and some tree T from trees. The pair (V, T) can only be chosen once overall.
He chooses a subtree T' from target that is rooted at V and is isomorphic to T (see notes for a definition if required).
The state of every edge in T' is toggled (i.e., if it was active, it becomes inactive; if it was inactive it becomes active).
Each time he follows the process he incurs a cost that depends on which tree he selected. If he selects trees[i] it costs him costs[i]. Petya also likes the number 5 and so no vertex in target will have more than 5 children. Return the minimum cost of activating all the edges in target or -1 if it is impossible to do so.
target and the trees in trees will be described using the same format:
 
The vertices are indexed sequentially starting with the root as vertex 0.
The parent of each vertex in index order is then written in a space-separated list. I.e., if the i-th number written (zero-indexed) is p[i], it means that there is a directed edge from vertex p[i] to vertex i in the tree. Since the root has no parent, the first number in the list will be -1 instead.
Definition
    
Class:
ActivateTree
Method:
minCost
Parameters:
vector <string>, string, vector <int>
Returns:
int
Method signature:
int minCost(vector <string> trees, string target, vector <int> costs)
(be sure your method is public)
    
 
Notes
-
Two trees T and T' are isomorphic if there exists a 1-to-1 mapping between the vertices of T and T', such that for each pair of vertices V1 and V2 in T, there is an edge (V1, V2) if and only if and edge exists between the corresponding vertices of T'. I.e., one tree can be transformed into the other simply by relabelling the vertices.
Constraints
-
target will contain between 1 and 46 characters, inclusive.
-
trees will contain between 1 and 5 elements inclusive.
-
Each element of trees will contain between 4 and 10 characters.
-
target and each element of trees will be single-space delimited lists of integers formatted without leading zeros, with no leading or trailing spaces.
-
target will contain between 2 and 16 integers, inclusive.
-
Each element of trees will contain between 2 and 5 integers, inclusive.
-
The first integer in target and in each element of trees will be -1.
-
target and each element of trees will describe valid trees as specified in the problem statement.
-
No vertex in the tree represented by target will have more than 5 children.
-
costs will contain the same number of elements as trees.
-
Each element of costs will be between 0 and 65536, inclusive.
Examples
0)
 
    
{"-1 0"}
"-1 0"
{5}
Returns: 5
 
1)
 
    
{"-1 0"}
"-1 0 0"
{5}
Returns: -1
 
2)
 
    
{"-1 0","-1 0"}
"-1 0 0"
{1,101}
Returns: 102
Petya can not use the first tree twice in the same position so he has to pay once for each of the trees.
3)
 
    
{"-1 0","-1 0","-1 0 3 0"}
"-1 0 3 0"
{5,10,21}
Returns: 20
Here it is cheaper to use the first tree twice and the second tree once than to use only the third tree.
4)
 
    
{"-1 0 1","-1 0 0","-1 0","-1 0 1 0 2"}
"-1 0 0 0 2"
{3885,13122,31377,21317}
Returns: 17007
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

접기