P2531 [SHOI2001] Three-Nation Go Team Competition

China invited the Korean and Japanese Go teams to a three-nation team competition. Korea and Japan each sent 5 top-tier players. Team China hopes to win the match, but those 10 players are very strong. However, as the host, after the other two teams have fixed their rosters and playing orders, Team China may decide its own roster and playing order to maximize its winning probability.

The rules are as follows: first, a draw determines the team that has a bye in round $1$. Then the No. $1$ players of the two non-bye teams play; the loser is eliminated. Thereafter, in each round, the previous winner plays against the smallest-index remaining player from the team that had the bye in the previous round. This continues until only one country still has players remaining; that country wins. > Note: When only two teams still have players not eliminated, ignore byes. In each round, the two smallest-index players from those two teams play, and the loser is eliminated.

The first line contains a number $n$ $(5 \le n \le 15)$, the number of candidates for Team China. Then follow $n$ lines, each containing $10$ numbers. In line $i+1$ $(1 \le i \le n)$, the $10$ numbers are the win probabilities of Chinese candidate $i$ against Korea No. $1 \sim 5$ and Japan No. $1 \sim 5$, respectively; each probability is $k$ $(0 \le k \le 1)$. Next are $5$ lines, each containing $5$ numbers. In line $n+i+1$ $(1 \le i \le 5)$, the $j$-th number is the win probability that Korea player $i$ defeats Japan player $j$.

Output a single line: the maximum winning probability for Team China, to $6$ decimal places.

Translated by ChatGPT 5