PuyoPuyo

SRM 484 · 2010-03-12 · by rng_58

SRM 484 · 2010-03-12 · by rng_58 · Dynamic Programming

Show categories

Class Name: PuyoPuyo

Return Type: int

Method Name: theCount

Arg Types: (int, int)

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.

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

2
2
Returns: 4

He must push the same type of Puyos twice.

2
4
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
58
Returns: 868294620

4
84
Returns: 621871151

5
8
Returns: 0

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PuyoPuyo with a public method int theCount(int L, int N) · 53 test cases · 2 s / 256 MB per case