Problem C

MU vs. Chelsea

Problem Description

Yay! My favorite football team, Manchester United (MU/The Red Devils), is going to have a match with team Chelsea (The Blues) tonight. This is my most anticipated match, and surely I don’t want to miss it. Before the match begins, Charlie (a statistic geek) asked me with the probability of each player on my favorite team to score a goal. As a perhaps-not-a-really-statistic-geek, I’m being curious with his question. Ok, there’s still enough time before the match begin. I’ll collect the data and do some paper and pencil works.

To solve this problem, I’ve come up with an idea. What I do need are Ferguson’s strategy (note: Ferguson is MU’s coach) and the statistic of several previous matches of MU vs. Chelsea.

For the Ferguson’s strategy, of course I know it very well. Any player who has the ball may either shoot, or pass it to other player in his team. Ferguson also won’t be happy at all if The Red Devils fooling around, so the team is not allowed to do more than 60 consecutive passes.

After doing careful analysis, I came up with this important information of The Red Devils team when they have match with The Blues team:

1. A matrix containing the success rate of each MU’s player to pass the ball to any player in their team. Note that a player can also pass the ball to himself (there’s a trick to do it).

2. The success rate of each MU’s player to score goal from his shot.

For this problem, let's consider that at the beginning, the ball will always be on MU goal keeper’s hand (player number 1). I’ve got the idea, I’ve got the data, but I can’t do the math. Now, please help me.

Input Speficication

The first line of input contains an integer T, the number of test cases follow.

Each test case consists of three parts:

The first part is a list of 11 player names (number 1 to 11), one player in each row. Player names will be no longer than 20 characters and may contain spaces.

The second part is a matrix P (11x11), the success rate of each player to pass the ball to any player in the team. The cell at i-th row and j-th column of the matrix means the success passing rate of player number i to player number j in percentage (0 <= P[i][j] <= 100).

The third part is the success rate of each player to score goal from his shot. The i-th element is the success shooting rate of player number i.

Output Speficication

For each case, print "Case #N:" (without quote) where N is the case number in a single line.

The next 11 lines contain the highest success rate of each player to score goal in descending order. If there is a tie, player with higher number will be printed first. For example, if there is a tie between player no. 10 and player no. 11, then print player no. 11 first and followed player no. 10.

Line Format: xx.xx% player_name where xx.xx represents the success rate of scoring goal.

See sample input/output for clarity.

1
Edwin van der Sar
Gary Neville
Patrice Evra
Owen Hargreaves
Rio Ferdinand
Wes Brown
Cristiano Ronaldo
Anderson
Louis Saha
Wayne Rooney
Ryan Giggs
69 82 17 79 66 42 15 28 79 30 2
55 6 71 70 44 35 66 60 87 36 55
65 74 92 13 97 22 3 40 74 43 61
39 19 10 89 78 36 79 32 89 59 65
51 40 49 69 15 16 96 4 42 14 6
79 13 51 29 92 23 63 2 46 5 14
49 59 100 70 47 3 89 4 81 29 98
95 99 99 97 37 44 37 75 71 87 84
26 73 50 19 62 33 18 76 26 38 18
87 68 21 64 5 35 26 68 53 48 36
47 25 49 20 92 37 47 45 83 51 94
8 46 18 52 28 66 97 45 85 95 88

Case #1:
67.15% Louis Saha
61.46% Cristiano Ronaldo
54.64% Ryan Giggs
49.62% Wayne Rooney
41.08% Owen Hargreaves
37.72% Gary Neville
27.72% Wes Brown
27.02% Anderson
18.48% Rio Ferdinand
11.40% Patrice Evra
8.00% Edwin van der Sar