| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Sparrow
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 71 Accepted Submission(s): 0
Problem Description
Sparrow is a kind of game. Four players (1,2,3,4) sits around a table. They take turns to act. Player i+1 is next to player i(i = 1,2,3) and player 1 is next to player 4
There are two categories of tiles in this game:
1) Simple tiles:
Simple tiles have 27 kinds: A1,A2...A9, B1,B2...B9 and C1,C2...C9. Each kind have 4 copies.
2) Honor tiles:
Honor tiles have seven kinds: E, S, W, N, Z, F, 0(zero) . Each of them also have 4 copies.
Several tiles can form a good set. There are 4 kinds of good set:
1) Pong is a set of three identical tiles.
2) Kong is a set of four identical tiles.
3) Chow is a set of three continuous SIMPLE tiles which have the same leading letter, such as A2,A3 and A4, or C7,C8 and C9. A1,B2 and A3 don't form a Chow because their leading letters are not the same.
4) Eye is a set of two identical tiles.
A tile can't belong to more than one good set.
A tile can be in one of three state:
1) On the wall.
2) Belongs to one player and faces down.
3) Belongs to one player and faces up.
At the beginning of the game, some tiles are on the wall, some tiles belong to players and face down. Then they play round by round. They draw tiles from the wall, discard some tiles, make some tiles face up, until a player declares that he/she holds a winning hand, or there is no tiles on the wall.
One player holds a winning hand, if and only if he can split his face-down tiles into zero, one or several sets of Pong/Chow, plus one set of Eye. A winning hand could be:
{E, E, E, N, N, N, 0, 0}, or {C1, C2, C3, B5, B5}
The one who declares a winning hand wins the game.
In each round, mostly , the round owner draw a tile from the wall and put it face-down. If the round owner finds out that the he/she has a winning hand, he/she will declare it and win the game. If no so, the round owner choose one (we call it T)of his face-down tiles to discard. Then comes the "declare phase". The other 3 players looks into their FACE-DOWN tiles, and may do 3 kinds of declarations below:
1) D0: declare a winning hand
If T can form a winning hand after one player owns it, this player can own T and declare a winning hand.
2) D1: declare a Pong.
If T forms a Pong set after one player owns it, then that player owns T, declares this Pong set, and changes the 3 tiles of the declared Pong set into face-up.
3)D2: declare a Kong.
Similar to D1, that player owns T , declare this Kong set, , and changes the 4 tiles of the declared Kong set into face-up.
In "declare phase", first they will ask each other whether someone want to declare a D0. If everyone give up, go on asking for D1. If no one declare a D1, go on asking D2.
If multiple declares happen at the same time, the player with the smallest id get T.
A declare will end a round. If one player declares, he gets T and becomes the owner of the next round. However, after D1 the new round owner does not draw a tile from the wall, he/she just discards a tile . After D2, the new round owner draws a tile then discards a tile.
If no one declare in the "declare phase", the player next to the round owner becomes the new round owner and draw a tile from the wall.
At any time, if someone gets a winning hand, the game ends. If one needs to draw a tile from the wall, but the wall has no more tiles, then the game ends with no winner.
One day, Alice and Bob suddenly want to play sparrow. But sparrow needs four players, and they could not find anyone in a moment. So they decide to play a two-man sparrow, that is, Alice will act as player 1 and player 3, and Bob will act as player 2 and player 4. Both of them control two roles at the same time.
Alice and Bob are very very clever children. And they both have a super gift: perspective. They can see any tile, even if it's face-down on the wall, or face-down owned by the other player!
(Now, you know why they can find no one playing sparrow with them ^o^ )
The game goes very exciting!(oh it makes nonsense, since they know what tiles the other holds, and they are both clever enough to find the other's strategy) And finally, it comes to such a situation that: after player 4 discards a tile, no one declare and player 1 (controled by Alice) becomes the round owner. Alice is ready to draw a tile.
There are only N tiles on the wall. All four players each have ten face-down tiles.
Decide whether Alice or Bob could win the game, if both of them act the optimal way.
There are two categories of tiles in this game:
1) Simple tiles:
Simple tiles have 27 kinds: A1,A2...A9, B1,B2...B9 and C1,C2...C9. Each kind have 4 copies.
2) Honor tiles:
Honor tiles have seven kinds: E, S, W, N, Z, F, 0(zero) . Each of them also have 4 copies.
Several tiles can form a good set. There are 4 kinds of good set:
1) Pong is a set of three identical tiles.
2) Kong is a set of four identical tiles.
3) Chow is a set of three continuous SIMPLE tiles which have the same leading letter, such as A2,A3 and A4, or C7,C8 and C9. A1,B2 and A3 don't form a Chow because their leading letters are not the same.
4) Eye is a set of two identical tiles.
A tile can't belong to more than one good set.
A tile can be in one of three state:
1) On the wall.
2) Belongs to one player and faces down.
3) Belongs to one player and faces up.
At the beginning of the game, some tiles are on the wall, some tiles belong to players and face down. Then they play round by round. They draw tiles from the wall, discard some tiles, make some tiles face up, until a player declares that he/she holds a winning hand, or there is no tiles on the wall.
One player holds a winning hand, if and only if he can split his face-down tiles into zero, one or several sets of Pong/Chow, plus one set of Eye. A winning hand could be:
{E, E, E, N, N, N, 0, 0}, or {C1, C2, C3, B5, B5}
The one who declares a winning hand wins the game.
In each round, mostly , the round owner draw a tile from the wall and put it face-down. If the round owner finds out that the he/she has a winning hand, he/she will declare it and win the game. If no so, the round owner choose one (we call it T)of his face-down tiles to discard. Then comes the "declare phase". The other 3 players looks into their FACE-DOWN tiles, and may do 3 kinds of declarations below:
1) D0: declare a winning hand
If T can form a winning hand after one player owns it, this player can own T and declare a winning hand.
2) D1: declare a Pong.
If T forms a Pong set after one player owns it, then that player owns T, declares this Pong set, and changes the 3 tiles of the declared Pong set into face-up.
3)D2: declare a Kong.
Similar to D1, that player owns T , declare this Kong set, , and changes the 4 tiles of the declared Kong set into face-up.
In "declare phase", first they will ask each other whether someone want to declare a D0. If everyone give up, go on asking for D1. If no one declare a D1, go on asking D2.
If multiple declares happen at the same time, the player with the smallest id get T.
A declare will end a round. If one player declares, he gets T and becomes the owner of the next round. However, after D1 the new round owner does not draw a tile from the wall, he/she just discards a tile . After D2, the new round owner draws a tile then discards a tile.
If no one declare in the "declare phase", the player next to the round owner becomes the new round owner and draw a tile from the wall.
At any time, if someone gets a winning hand, the game ends. If one needs to draw a tile from the wall, but the wall has no more tiles, then the game ends with no winner.
One day, Alice and Bob suddenly want to play sparrow. But sparrow needs four players, and they could not find anyone in a moment. So they decide to play a two-man sparrow, that is, Alice will act as player 1 and player 3, and Bob will act as player 2 and player 4. Both of them control two roles at the same time.
Alice and Bob are very very clever children. And they both have a super gift: perspective. They can see any tile, even if it's face-down on the wall, or face-down owned by the other player!
(Now, you know why they can find no one playing sparrow with them ^o^ )
The game goes very exciting!(oh it makes nonsense, since they know what tiles the other holds, and they are both clever enough to find the other's strategy) And finally, it comes to such a situation that: after player 4 discards a tile, no one declare and player 1 (controled by Alice) becomes the round owner. Alice is ready to draw a tile.
There are only N tiles on the wall. All four players each have ten face-down tiles.
Decide whether Alice or Bob could win the game, if both of them act the optimal way.
Input
First line is an integer Q: the number of input data set.
Then comes Q input set, each with 5 lines. The first 4 lines each describe ten tiles of player 1..4.
The fifth line of each dataset describes the tiles on the wall. First the integer N, then comes N tiles in order.
There may be extra blank lines and spaces in the input file. Q<=20, and N<=4.
Then comes Q input set, each with 5 lines. The first 4 lines each describe ten tiles of player 1..4.
The fifth line of each dataset describes the tiles on the wall. First the integer N, then comes N tiles in order.
There may be extra blank lines and spaces in the input file. Q<=20, and N<=4.
Output
If Alice could win the game, print "Alice win";
If Bob could win the game, print "Bob win";
Otherwise, print "tie".
If Bob could win the game, print "Bob win";
Otherwise, print "tie".
Sample Input
3 A1 A1 A1 A2 A2 A2 A3 A3 A3 A8 B1 B1 B1 B2 B2 B2 B3 B3 B3 B4 B4 B5 B5 B5 B6 B6 B6 B8 B8 B8 Z Z Z F F F S S S N 2 A5 B4 A1 A1 A1 A2 A2 A2 A3 A3 A3 B8 B1 B1 B1 B2 B2 B2 B3 B3 B3 B4 B4 B5 B5 B5 B6 B6 B6 B8 B8 B8 Z Z Z F F F S S S N 2 A5 B4 A1 A1 A1 A2 A2 A2 A3 A3 A3 B8 B1 B1 B1 B2 B2 B2 B3 B3 B3 B4 B4 B5 B5 B5 B6 B6 B6 B8 B8 B8 Z Z Z F F F S S S N 1 Z
Sample Output
Bob win Alice win tie
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-04-19 22:59:03, Gzip enabled |
Administration |