407227: GYM102697 198 Bracket Challenge

It is March, and the NCAA basketball tournament is happening soon. You're trying to figure out which teams have the best chances at winning the tournament.

Leading "bracketologists" have calculated, for each team, their probability of winning against each of the other teams. In other words, you know, for every pair of teams, the probability of each of the two teams winning in a game between the two teams, which can be represented by a table (more information in the input section).

There are $$$n$$$ teams in the tournament. $$$n$$$ will always be a power of two. Each team is given a unique number (their "seed"), from 1 to $$$n$$$.

In the first round of the tournament, the team with seed $$$s$$$ plays the team with the seed $$$n$$$ - $$$s$$$ + 1. For example, in the first round of an 8-team tournament, the 1 seed will play the 8 seed, the 2 seed will play the 7 seed, and the 3 seed will play the 6 seed.

After the first round, the teams that lost their match are eliminated from the tournament, and the teams that won their match move on to the next round.

In the next round, there are $$$\frac{n}{2}$$$ teams still left in the tournament. If every team with a lower numbered seed won each game, the second round proceeds similarly to the first round. For example, in the second round of an 8 player tournament where every lower numbered seed won each first round game, the 1 seed plays the 4 seed, and the 2 seed plays the 3 seed.

If a higher numbered seed won a first round game, they will play in the second round game that the team they beat would have played in. For example, if the 7 seed beat the 2 seed in the first round of an 8 player tournament, then the 7 seed would play the 3 seed in the second round, or the 6 seed, if the 6 seed beat the 3 seed in the first round.

This process repeats until the finals, when the winner of the finals wins the whole tournament.

Given the probability table described above, sort the teams by their probability to win the entire tournament.

The first line contains a single positive integer $$$n$$$: the number of teams in the tournament. $$$n$$$ is guaranteed to be a power of two.

The next line contains $$$n$$$ space-separated strings: the name of each team in the tournament.

The next $$$n$$$ lines each contain $$$n$$$ space-separated integers. The $$$j$$$th integer on the $$$i$$$th line represents the probability that the $$$i$$$th seeded team will beat the $$$j$$$th seeded team. The probabilities will be given as an integer percentage out of 100. The probability that a team will beat themselves will be given as 50

Output $$$n$$$ lines. Each line should contain the name of each team, a space, and the probability that the team will win the tournament, given as a percentage out of 100, rounded to the nearest integer. Sort the teams from highest to lowest, based on their probability of winning the tournament.

Note that you should round your answers after sorting the list of teams and their win probabilities.

4
Syracuse Michigan Duke UNC
50 78 47 52
22 50 21 19
53 79 50 60
48 81 40 50

Duke 45
Syracuse 28
UNC 23
Michigan 4

8
Syracuse Duke Louisville UNC Virginia Pittsburgh Indiana Kansas
50 54 62 51 55 97 83 35
46 50 52 43 57 94 65 29
38 48 50 34 48 87 81 31
49 57 66 50 54 96 77 23
45 43 52 46 50 90 55 11
3 6 13 4 10 50 33 1
17 35 19 23 45 67 50 15
65 81 69 77 89 99 85 50

Kansas 40
Louisville 18
Duke 14
Syracuse 11
UNC 11
Virginia 5
Indiana 2
Pittsburgh 0