Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Table Tennis

By BlackBeard · Limits 1s, 512 MB

One day you have invited Sohel bhai to come to East West University to see an intra-University table tennis match. Sohel bhai likes table tennis very much. So, he came to give you company.

In the intra-university table tennis match there were 16 players who played in the 1st round: in the 2nd round, 8 players: in the 3rd round, 4 players and in the final round obviously there are 2 players from whom 1 winner will be determined. So the game format would look like this:

A - - - - +
	+ - - - - +
B - - - - +	|
		+ - - - - +
C - - - - +	|	|
	+ - - - - +	|
D - - - - +		|
			+ - - - - +
E - - - - +		|	|
	+ - - - - +	|	|
F - - - - +	|	|	|
		+ - - - - +	|
G - - - - +	|		|
	+ - - - - +		|
H - - - - +			|
				+ - - - -?
I - - - - +			|
	+ - - - - +		|
J - - - - +	|		|
		+ - - - - +	|
K - - - - +	|	|	|
	+ - - - - +	|	|
L - - - - +		|	|
			+ - - - - +
M - - - - +		|
	+ - - - - +	|
N - - - - +	|	|
		+ - - - - +
O - - - - +	|
	+ - - - - +
P - - - - +

Probability of every possible XXX vs. YYY will be given (total 16×16 = 256) which is sufficient to compute the probability of a given player's victory. Suppose P(M vs. N) = 80% , P(O vs. R) = 60%, P(M vs. O) = 70% and P(M vs. R) = 90%; then the probability of M getting to the 3rd round is 80%*(70%*60% + 90%*40%) = 62.4%.

In the middle of gossiping , Sohel bhai asked you to find out the chances of the players winning the competition. Now, you are to write a program to compute the chances of every player winning the competition.

Input

There will be only one test case per file. The test case will start with 16 lines with the names of 16 players from top to bottom according to the outline given above. The names will be one word and at most 20 characters long. Then there will be a 16 × 16 matrix M given where Mi,j will give the probability in percent of the ith player defeating jth player.

Note that, matches will not end in draw and Mi,j + Mj,i = 100 for all i, j.

Output

The output will contain 16 lines where each line consists of the name of the players followed by a space followed by its probability of winning the completion. The order of names of players should be the same as of input.

Sample

InputOutput
Marky
Ricky
Danny
Terry
Mickey
Davey
Timmy
Tommy
Joey
Robby
Johnny
Brian
Willy
Chuck
Skyler
Sean
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
Marky p=8.54%
Ricky p=1.60%
Danny p=8.06%
Terry p=2.79%
Mickey p=4.51%
Davey p=7.50%
Timmy p=8.38%
Tommy p=1.56%
Joey p=9.05%
Robby p=3.23%
Johnny p=13.72%
Brian p=3.09%
Willy p=13.79%
Chuck p=3.11%
Skyler p=5.53%
Sean p=5.53%

Discussion

Statistics


75% Solution Ratio

bqi343Earliest, Aug '16

Deshi_TouristFastest, 0.0s

bqi343Lightest, 131 kB

Deshi_TouristShortest, 1139B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.