Time Limit: 10 Seconds
Memory Limit: 32768 KB
Zuma is one of my favourite games of Fantasy Games series. In the game a lot
of balls of different colors will enter the screen continuous, and the
balls onscreen are rolling by a fixed track in a queue. You can control
the stone frog located at the center of screen to fire balls. The balls
fired can be inserted into the rolling balls queue. When there is a group
of 3 or more balls of the same color touching, they explode! You should
eliminate all the balls before they reach the skull which lies on the
end of the track.
Let's consider a simplified game mode. There is a queue of balls of different
colors given. At each time you can fire a ball of arbitrary color into
the queue at arbitrary position (either between two balls or at one end
of the queue) . Arbitrary means that you can choose the color and the
position on your behalf. When there is a group of 3 or more balls of the
same color touching, they explode, and you will get a number of points
which equals to the square of the length of the group. Explosion causes
the balls on either side to slide together, perhaps chain-reacting into
There are some limitations following:
- You can only fire a ball of a certain color to a position where there is
at least one ball of the same color touching. That is, after you fire the
ball into the queue, there should be at least one ball of the same color touching
the ball you fired.
- There may be some groups of 3 or more balls of the same color touching at
the initial situation. These balls will explode just when another ball (not
belonging to the group but of the same color) or another group of balls of
the same color touches them.
When the game ends (all the balls are eliminated), how many points you can
get at most?
Input contains multiple test cases. Each test case there is one line of nonempty
capital letters (A to Z). Each character specifies one ball of the color represented
by the letter. The length of each line is no more than 200.
There is one line for each test case, which is the number of points you can
get at most in the game.
Please give me a key then I can open
up and get into your heart.
Author: CHEN, Shixi
Source: Online Contest of Fantastic Game