SanguoSHA

SanguoSHA is a very popular game. The rules of SanguoSHA are too complex for me to describe it in English, so just let me simplify it a lot. ^ ^.

In this custom game we have several rules shown below, and you should read carefully:
Part I--Identifies:
1): There are at most 8 players while at least 4;
2): There are 4 roles: Lord, Minister, Rebel, and Traitor.
3): The goal of the Lord and Ministers is to kill all of the Rebels and the Traitor.
4): The goal of the Rebel is to kill the Lord.
5): The goal of the Traitor is to make himself alive until the game over.
6): There is only 1 Lord.
7): There is only 1 Traitor.
8): There will be at least 1 Rebel.
9): There will be at least 1 Minister.
10): Every player know the total remain number of Rebel and Minister.

Part II--How to determine the game over and who wins:
1): If the Lord is alive, and there is neither alive Rebel nor Traitor, then the game over, and the Lord and Ministers win.
2): When the Lord is killed by someone, the game over, if there is no one but the Traitor alive, then the Traitor wins; otherwise, the Rebels win.

Part III--How to play in this custom game:
1): At first, the roles of all players except for the Lord are hidden, they only know their own roles. That means players have to conjecture others' role by analysing their behavior.
2): In each round, all alive players play one by one. The player1 plays first, then player2...
3): In each player's turn, the player can choose one and only one player to attack. The probability of killing the chosen one is P.
4): When a player is killed, his role should be announced.

Part IV--How to analysis player's behaviors:
1): The Lord is always be considered as Lord.
2): A player will be considered as Rebel when he attack the Lord.
3): A player will be considered as Rebel when he attack one which considered as Minister before all Rebels are eliminated.
4): A player will be considered as Minister when he attack one which considered as Rebel.
5): A player will be considered as Traitor when he have been considered as Minister and Rebel.
6): The players are not clever enough, they can't analysis other behaviors.

Part V--The attack strategy of each role:
Eliminated player couldn't do anything.
No one will attack eliminated player or himself.
For each strategy, all eligible player have equal probability of being attacked.
The Rebel will choose one of the following strategies by order:
1)The Lord or Ministers if some players are considered as Minister.
2)The Lord or Traitor if a player is considered as Traitor.
3)The Lord.
The Lord and Ministers will choose one of the following strategies by order:
1)The player which be considered as Rebel.
2)The player which be considered as Traitor.
3)If all rebel roles are eliminated, then attack anyone except Lord.
4)The player with unknown role.
The Traitor will choose one of the following strategies by order:
1)The player which be considered as Minister if alive Minister number more than alive Rebel number.
2)The player which be considered as Rebel if alive Rebel number not less than alive Minister number.
3)Anyone expect the Lord.
4)The Lord.

Such information will be given:
1): The number of players.
2): Each player's identify.
3): The probability of killing the chosen one.
For each role, you should calculate the probability of winning within 10 round.

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
Each case consists of three lines, the first line is an integer N(4<=N<=8), indicating the number of players.
The second line contains N integers, player1,player2...playern, indicating the role of each player.(The first player will always be the Lord).(0, 1, 2, 3 indicating Lord, Minister, Rebel, and Traitor respectively.)
Then the third line contains a real number P(0<P<1).

For each case, output the number of case and the win probability of the 4 roles.Answers are rounded to 3 numbers after the decimal point.(as shown in the sample output)

2
4
0 1 2 3
0.5
4
0 3 2 1
0.5

Case 1:
Lord and Minister:0.549
Rebel:0.334
Traitor:0.118
Case 2:
Lord and Minister:0.501
Rebel:0.334
Traitor:0.166

NotOnlySuccess

2011 Alibaba Programming Contest