Problem Statement |
| | Cat Taro is playing a game called PuyoPuyo. In this game, he uses 4 types of colored balls called Puyos (Red, Blue, Green and Yellow) and a cylinder. He pushes Puyos into the cylinder. When he pushes a Puyo into the cylinder, it falls on top of the topmost Puyo already in the cylinder (it falls to the bottom of the cylinder if it's empty). If the cylinder contains at least L Puyos and the topmost L Puyos are the same type, the topmost L Puyos disappear.
Initially the cylinder is empty. Return the number of different ways to push N Puyos into the cylinder, so that the cylinder becomes empty after the pushes, modulo 1,000,000,007. |
| |
Definition |
| | | Class: | PuyoPuyo | | Method: | theCount | | Parameters: | int, int | | Returns: | int | | Method signature: | int theCount(int L, int N) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Two ways are different if there exists an i such that i-th pushed ball is different in one way than it is in the other. |
| |
Constraints |
| - | L will be between 2 and 10, inclusive. |
| - | N will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4 | | He must push the same type of Puyos twice. |
|
|
| 1) | |
| | | Returns: 28 | There are 4 ways to push Puyos of the form "XXXX".
There are 12 ways to push Puyos of the form "XXYY".
There are 12 ways to push Puyos of the form "XYYX". In this case, the cylinder changes as follows: (right represents the top of the cylinder)
"" (initially the cylinder is empty)
"X" (push X-type Puyo)
"XY" (push Y-type Puyo)
"XYY" (push Y-type Puyo)
"X" (two topmost Y-type Puyos disappear)
"XX" (push X-type Puyo)
"" (two topmost X-type Puyos disappear)
In total, there are 4 + 12 + 12 = 28 ways. |
|
|
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |