PROBLEM STATEMENT
In a popular game, a ball is dropped from the top of a triangle of cells containing n rows. The
ball keeps falling down row by row until it reaches the bottom of the triangle. In each row, the
ball can fall either left or right.
The first row contains one cell, the second contains two, and so on. The game looks like the
following picture (where a cell is the space between
two consecutive points in a row):
The rows are numbered from top to bottom starting from zero, and the cells in each row are
numbered from left to right
starting from zero. Note that row i will have i+1 cells numbered 0 to i, and if the ball
is on cell k of row i, it will either fall left to cell k of row i+1, or right to cell k+1 of row
i+1.
Given a vector cells, containing a list of cells, and an int n, the number of rows in the
triangle,
return the number of paths in which the ball passes through all of the given cells. Each element
of cells will be formatted " " (quotes for clarity), where is the cell's row, and
is the cell's position within that row.
DEFINITION
Class:FallingBall
Method:howMany
Parameters:vector , int
Returns:int
Method signature:int howMany(vector cells, int n)
CONSTRAINTS
-cells will have between 1 and 50 elements, inclusive.
-n will be between 1 and 30, inclusive.
-Each element of cells will be formatted " ", where and are each integers,
with no extra leading zeros.
-Each in cells will be between 0 and n-1, inclusive.
-In each element of cells, will be between 0 and , inclusive.
EXAMPLES
0)
{"3 2","5 2"}
7
Returns: 6
This example is shown in the picture above. There are 3 ways to reach the cell (3,2), then only
one way to reach the second cell (5,2), and two more
ways of reaching the bottom. That gives a total of 6 ways of passing through
the cells.
1)
{"0 0","0 0"}
30
Returns: 536870912
All the possible paths pass through the cell (0,0).
2)
{"0 0","29 0"}
30
Returns: 1
There is only one way to reach the bottom-right cell.
3)
{"10 0","10 1"}
15
Returns: 0
Two different cells in the same row can never be touched in the same path.
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.
| | | | |