Description

While Niflheimr was cleaning up the trash inside his computer, he found an old game - Zuma. (Refer to the end for detail if you don't know what is Zuma.)
He played Zuma for a while, and he come up with a cool idea: why not combine binary tree with the original Zuma game?

After a few days of thinking, he finally designed a new game: BiZuma!
In this new game, there is a binary tree consists of colored balls, and a stone frog in front of the tree root.
At the beginning, there will be a black ball (color number = -1) located at tree root. Players can fire balls to the desired places in the tree. For each firing, there will be a moving sequence.
For example, "LRRLR" is a possible moving sequence. We can interpret the moving sequence as follow (let the length of the sequence be "len"):

1. The initial place is root.
2. For i in [0, len-1):
   • If sequence[i] is 'L'('R'), then we move to the left(right) child of the current ball.
3. Now we reach the ball where we will insert a new ball on its left(right) child.
   • If sequence[len-1] is 'L'('R'), then we insert a new colored ball between the current ball and its left(right) child (you can view it as a linked list, and we insert a node between current node and its left(right) child).
   • The original left(right) child will become the left(right) child of the new colored ball.
   • If the current ball has no left(right) child, then just insert the new ball as the left(right) child of the current ball.
4. After inserting the new ball, there might be some explosions.
   • If a ball has same color with its left(right) child, then we destroy the ball itself and its left(right) subtree, moving its right(left) subtree to the original place of the ball.

Niflheimr wants to write this PC game, but he hurt his finger while playing Zuma. So he asked you to help him to complete the task.

Implement void shoot(...) and remember to #include "function.h" !!!

 

Reference:

Zuma is an old PC game. In the game, there is a stone frog in the middle of the screen, and some colored balls in a given path; the objective is to eliminate all the balls on the given path.
Players can eliminate the balls by firing a colored ball from the stone frog's mouth toward the chain of balls. When three or more of the same color come in contact, they explode, possibly triggering other explosions as part of the chain reaction.
The player wins the game when the player eliminate all the colored balls on the screen.
(extracted from Wikipedia)

Input

There is an integer N at the first line of input, representing the times of ball firing.
In the next N lines, each line is of the following form:
    "[color] [moving sequence]"
    [color] is an integer, [moving sequence] is a char sequence.
    Insert a new ball with color [color] by traversing down the tree by the [moving sequence] (use the law described above).

Output

Do the preorder traversal of the binary tree. For each ball, print out the color of the ball when visited first time.
There is a space after each color, and there will be a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11861.c

Partial Judge Header

11861.h

Tags

Add Tag

Discuss