|
|
|
Cards Game - Kitty Fishing source: ACM ICPC, 1997-98 Asia Regional contest
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.
A: 4,2,3 B: 2,1,3,4 Cards on the table: 1.
Second: B gives out 2.
A:4,2,3 B:1,3,4 Cards on the table: 1,2
Third: A gives out 4.
A:2,3 B:1,3,4 Cards on the table 1,2,4
Forth: B gives out 1.
A:2,3 B:3,4 Cards on the table: 1,2,4,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:
A: 2,3 B: 3,4,1,4,2,1 Cards on the table: NULL
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".
Input
The input file 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 file. No input lines follow that line.
Output
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.
Sample Input
30 5 8 5 6 5 7 3 4 6 2 1 7 7 1 2 1 0 3 8 7 8 8 5 6 3 6 2 3 2 4 4 1 4 0 0
Output for the Sample Input
Case 1: 1 5 7 3 5 3 3 6 6 1 1 4 8 8 8 5 8 6 7 5 6 2 2 4 7 2 1 3 4 2 7 4
|
|
----- END of Problem Statement ----- |
|
I solved this problem and the solution is available for you all in the Zip format. With C source code, you will find the README file which will explain the algorithm, and some miscleanious information about the problem, if any, and the solution given. NOTE: I don't claim that the given solutions are either completely correct or the only possible solutions. Though I tried my best to solve them, the problems of ACM standard will have many hidden constraints, which generally progrmmers may miss. And I am not an exception! If you find any thing of that sort, please bring it to my notice. I will try my level best to solve it. |
|
|
|
[Home] [Ramu] [Gnet] [CP-I] [CP-II] [Apti] [Study Material] [Software] [Resume] [Photos] [Contact] [MMS] [BITS] [Interface] |
|
. |