{"raw_statement":[{"iden":"statement","content":"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.\n\nLeading \"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).\n\nThere 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$.\n\nIn 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.\n\nAfter 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.\n\nIn 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.\n\nIf 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.\n\nThis process repeats until the finals, when the winner of the finals wins the whole tournament.\n\nGiven the probability table described above, sort the teams by their probability to win the entire tournament.\n\nThe first line contains a single positive integer $n$: the number of teams in the tournament. $n$ is guaranteed to be a power of two.\n\nThe next line contains $n$ space-separated strings: the name of each team in the tournament.\n\nThe 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\n\nOutput $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.\n\nNote that you should round your answers after sorting the list of teams and their win probabilities.\n\n"},{"iden":"input","content":"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"},{"iden":"output","content":"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."},{"iden":"examples","content":"Input4\nSyracuse Michigan Duke UNC\n50 78 47 52\n22 50 21 19\n53 79 50 60\n48 81 40 50\nOutputDuke 45\nSyracuse 28\nUNC 23\nMichigan 4\nInput8\nSyracuse Duke Louisville UNC Virginia Pittsburgh Indiana Kansas\n50 54 62 51 55 97 83 35\n46 50 52 43 57 94 65 29\n38 48 50 34 48 87 81 31\n49 57 66 50 54 96 77 23\n45 43 52 46 50 90 55 11\n3 6 13 4 10 50 33 1\n17 35 19 23 45 67 50 15\n65 81 69 77 89 99 85 50\nOutputKansas 40\nLouisville 18\nDuke 14\nSyracuse 11\nUNC 11\nVirginia 5\nIndiana 2\nPittsburgh 0\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n = 2^k $ for some $ k \\in \\mathbb{N} $ be the number of teams.  \nLet $ T = \\{t_1, t_2, \\dots, t_n\\} $ be the set of teams, indexed by seed $ i \\in \\{1, \\dots, n\\} $.  \nLet $ P = [p_{ij}] \\in [0,1]^{n \\times n} $ be the probability matrix where $ p_{ij} $ is the probability that team $ i $ beats team $ j $, with $ p_{ii} = 0.5 $.  \n\nLet $ \\mathcal{R}_0 = \\{1, 2, \\dots, n\\} $ be the initial seed ordering.  \nFor round $ r \\in \\{1, \\dots, k\\} $, define the bracket structure recursively:  \n- In round $ r $, the $ n / 2^{r-1} $ remaining teams are paired such that the winner of the match between seeds $ a $ and $ b $ (from round $ r-1 $) faces the winner of the match between seeds $ c $ and $ d $, where the original bracket structure is preserved: teams are grouped into blocks of size $ 2^{k-r+1} $, and within each block, the top half (lower seeds) plays the bottom half (higher seeds) in a fixed hierarchical structure based on initial seeding.  \n\nLet $ W_i \\in [0,1] $ denote the probability that team $ i $ wins the entire tournament.\n\n**Constraints**  \n1. $ n \\in \\{2, 4, 8, 16, 32, 64, 128, 256\\} $ (power of two).  \n2. $ p_{ij} \\in \\{0, 1, \\dots, 100\\} / 100 $, with $ p_{ij} + p_{ji} = 1 $ for $ i \\ne j $, and $ p_{ii} = 0.5 $.  \n3. Tournament structure follows single-elimination bracket with fixed initial pairing: seed $ s $ vs seed $ n - s + 1 $ in round 1. Subsequent rounds preserve bracket integrity: winners advance to the slot their defeated opponent would have occupied.\n\n**Objective**  \nCompute $ W_i $ for each team $ i \\in \\{1, \\dots, n\\} $, where:  \n$$\nW_i = \\sum_{\\text{all valid tournament paths } \\pi \\text{ where } i \\text{ wins}} \\prod_{\\text{matches in } \\pi} p_{\\text{winner} \\to \\text{opponent}}\n$$  \nThen, sort the teams by $ W_i $ in descending order.  \nOutput each team name and $ \\text{round}(100 \\cdot W_i) $ as an integer percentage, one per line.","simple_statement":"You are given n teams (n is a power of 2), each with a seed from 1 to n.  \nYou have a table showing the probability (as a percentage) that team i beats team j.  \n\nThe tournament is single-elimination:  \n- Round 1: seed 1 vs seed n, seed 2 vs seed n-1, etc.  \n- Winners advance.  \n- In each next round, winners keep playing in the bracket position of the team they beat.  \n\nCalculate the probability each team wins the whole tournament.  \nOutput the teams sorted by winning probability (highest to lowest), with their name and rounded win probability (as integer percentage).","has_page_source":false}