The 7th(2012) ACM Programming Contest of HUST - Onsite Contest(Semilive)

From: 2012-12-16 12:10:00 To: 2012-12-16 17:10:00 Now: 2017-09-24 21:43:15 Status: Public

D - CardGame

Time Limit: 1s Memory Limit: 128MB

Submissions: 22 Solved: 2
Description
Since SheepGod joined the ACM team, his teammates, jianhe25 and tclsm, started suffering a bad time, because SheepGod was training every day, and they didn’t have time to relax themselves. As a lazy boy, lkq wants to make some change.
At the last weekend, lkq managed to hold a card game activity. lkq thought it’s not good to think too much when relaxed, so he played the famous card game UNO with with SheepGod and his teammates.
 
In order to simplify the problem, we use some special rules for UNO here. Even if you are a greater UNO card game player, please read the following description carefully.
1. General idea about UNO
UNO is a card game in which 4 players compete to be the first to “gone out”(played all cards from his hand).
Players take turns drawing cards and play a card from his hand according to the rule(we will explain it later),the first player to play all his cards will be the winner and the game ends.
When a player should draw cards but the deck doesn’t have enough cards, the game ends as a draw game.
 
2. The Cards in UNO
The deck consists of 108 cards, of which there are 100 ordinary cards, and the remaining 8 cards are wild cards.
 
Every ordinary card has its color and content. There are 4 colors: red, green, blue and yellow. Each color has 25 cards, their contents are: two of rank 1 to rank 9, one of rank0, two of “Reverse” cards, two of “Skip” cards and two of “Draw Two” cards, as a total number of 25 cards. These ordinary cards are shown below.


Figure 1. Ordinary cards
 
Wild cards consists of “Wild Draw Four” cards and “Wild Change Color” cards, the deck having four of each. A wild card doesn’t have a regular color. Wild cards are shown below.

Figure 2. Wild cards
 
3. Play rules
When the game starts, the players take turns to draw a card from the deck for seven time, so each player will have 7 cards then.
At first, player 1 flips the top card of the deck, if the card is a wild card, then discard it and flips the top card again, until it’s not a wild card, and this is the first played card in the game.
Play begins clockwise, unless that player was skipped or play was reversed(see below). A player on his turn should play a card from his hand that matches either the color or content(or both) of the last played card. A wild card may be played instead, though the “Wild Draw Four” card has some restrictions(see below).
If the player doesn’t have a playable card, he must draw one from the deck. Once a player has drawn, if the new card is playable, then he have to play it.

To simplify the problem, when a player has more than one playable cards, he will obey the following priority rule to play:
         i. Content priority goes first: Draw Two > Skip > Reverse > 9 > 8 > …> 0 > Wild Change Color > Wild Draw Four.
         ii. When two cards have the same content, color priority goes second: Red > Yellow > Green > Blue.

Please Pay attention to effects of these cards when played:
Skip: When played, the next player in rotation loses their turn, and the following player then may play.
Reverse: When played, the rotation of play is reversed, i.e. clockwise play changes to counter-clockwise, and vice-versa.
Draw Two: When this card is played, the next person to play must draw 2 cards and forfeit his turn.
Wild Change Color: When played, the player may call a color (red, yellow, green or blue). Play continues with the next player obliged to play a card of that color.
Wild Draw Four: The player using this card calls a new color, and the next player draws four cards and loses their turn. This card may only be played when the holder does not hold a card having color matching the active color (last played card or called color after a wild card).
When played a wild card, the player will obey the following rule to call a color:
    i. Player chooses the color that he owns most in his hand.
    ii. When two colors have the same occurrence, color priority goes second: Red > Yellow > Green > Blue.
 
Now the problem is that given the sequences of the deck in each round, can you calculate who is the winner of the round? In another word, please find out who is the first one that goes out, or the game comes to a draw game. The initial clockwise order of the four players to draw cards is, SheepGod, jianhe25, tclsm and lkq.
Input
 First line of the input is a single integer T(1 <= T <= 100), indicating they plays UNO for T rounds.
For each test case, there’s only one line, where gives the order of 108 cards.
We use two characters to represent a card, one for color, the other for content. For more details, please see the table below.
 
Color Represent
Red R
Yellow Y
Green G
Blue B
(Wild) W
Content Represent
0~9 number according
to the content
Draw Two D
Reverse R
Skip S
Wild Draw Four F
Wild Change Color C
 
Output
For each test case, output a single line in the form of "Case #X: Winner is NAME!" if someone wins at this round, or "Case #X: Draw game!" if no one wins. X here means the number of test cases starting from 1, NAME is the name of player who wins.
Sample Input
2
GS YD R1 G4 B9 B4 B5 WC GD R9 B3 G5 R6 R7 B8 G1 WC Y8 Y8 Y2
Y4 R2 WC G1 Y9 R4 WF Y1 R2 B6 B9 G7 G9 YR R8 B7 Y7 Y6 G7 G2
GR G6 G6 YR RD R0 Y1 Y4 R9 Y3 G4 RS R3 B3 B4 RR B7 GS YD B1
G8 R5 R1 Y6 YS BR RR Y0 Y5 B5 Y9 R4 WF B6 GD WC BS BD G5 G0
R7 BD Y2 R8 G8 R6 RS R3 Y5 B0 G9 YS B8 GR G3 BS WF Y3 G2 BR
B2 R5 RD Y7 WF B1 G3 B2 
R0 Y8 R5 R1 YS YR RS G4 GS R7 YD WC WF WC GR Y3 R4 G1 G6 G6
R5 R6 G5 Y0 YR G1 Y7 G8 G4 BR Y9 Y8 Y4 G8 BD R4 WF B7 Y2 WC
RS WF R3 G9 B9 Y1 R6 G7 B8 B7 BD Y3 Y5 RD G3 Y6 G9 Y6 BS B4
Y7 G2 R3 B3 B9 B5 G5 YD BS R1 Y9 B8 B5 WC B4 R9 RR B6 G0 R2
GS B1 R8 WF G3 Y4 B6 Y2 R7 GD R9 B3 Y1 R8 B2 Y5 G2 GD G7 R2
RD B0 RR YS GR B1 B2 BR
Sample Output
Case #1: Winner is SheepGod!
Case #2: Winner is lkq!
Hint
Source
The 7th(2012) ACM Programming Contest of HUST Problem Setter: Kangqi Luo