P1769 Single-Elimination Tournament

The single-elimination system is a very brutal competition format. There are $2^n$ players numbered $1, 2, 3, \cdots, 2^n - 1, 2^n$, and they will compete for $n$ rounds. In each round, after sorting all players participating in that round by increasing index, the $1$-st plays the $2$-nd, the $3$-rd plays the $4$-th, the $5$-th plays the $6$-th, and so on. Only the winner of each match advances to the next round (there are no ties). Thus, each round eliminates half of the players. After $n$ rounds, exactly one player remains, who is the champion. Now you are given, for every pair of players, the probability that one beats the other. Please predict which player has the highest probability of winning the championship.

The first line contains an integer $n$ ($1 \le n \le 10$), the total number of rounds. Then follow $2^n$ lines, each containing $2^n$ integers; in line $i$, the $j$-th number is $p_{i,j}$. The constraints are $0 \le p_{i,j} \le 100$, $p_{i,i} = 0$, and $p_{i,j} + p_{j,i} = 100$. Here $p_{i,j}$ denotes the probability (in percent) that player $i$ defeats player $j$.

Output a single integer $c$, the index of the player whose probability of becoming the champion is the highest (if there are multiple such players, output the smallest index).

- $30\%$ of the testdata satisfies $n \le 3$. - $100\%$ of the testdata satisfies $n \le 10$. Source: NOI Guide 2010 Senior (01). Translated by ChatGPT 5