ZOJ Problem Set - 1452
There is a simple two-player card game called "Kitty Fishing". When the game begins, player A and B have the same number of cards. Then each gives out one card in turn. Each card given out on the table should be laid overlapped one by one. When the card newly given out finds a card which has the same value on the table, the player who gives out the card will take the cards between the two same cards following the order the cards on the table, and put them to the back of his cards. The same player continues to give out next cards. Player giving a card called a turn. Note: Do not change the order of your cards.
The following is an example.
At the beginning:
A has cards 1,4,2,3 and B has cards 2,1,3,4
First: A gives out 1.
Second: B gives out 2.
Third: A gives out 4.
Forth: B gives out 1.
The card '1'given out by B is the same as the first one of the cards on the table. So B takes the cards following the turn of '1,4,2,1'. Then it will be:
In this example, A and B have four turns.
If one of the players has given out all of his cards, he will lose the game, and the other one is the winner. The game is over.
Write a program that will play the game of "Kitty Fishing".
The input contains one or more data sets. Each data set consists of three lines: The first line contains an integer which gives out the turns you should play, and the next two lines are cards which A and B have. Each one's cards will be ended with the number 0.
A line which contains a single 0 will end the input. No input lines follow that line.
If the game has been over before the turns, just write out the winner's name. If the game has not been over, write out the cards two players have in the order in their hands and the cards on the table.
Source: Asia 1997, Shanghai (Mainland China)