P5699 [NOI2008] Tournament Schedule

With the Olympics approaching, students are becoming more and more enthusiastic about sports. As NOI2008 is coming, the school is planning to hold a table tennis tournament. Student Z, a hardcore table tennis fan, sees this as a great chance to show his skills, so he eagerly signs up. This table tennis tournament uses a single-elimination format: winners advance. There are exactly $n$ students signed up ($n$ is an integer power of $2$, so we may assume $n = 2^k$). Therefore, after the first round, $2^{k-1}$ students will be eliminated and the other $2^{k-1}$ students will advance to the next round; after the second round, $2^{k-2}$ students advance to the next round, and so on, until after $k$ rounds the champion and runner-up are decided. Specifically, everyone has an initial ID from $1\sim n$. Student Z has ID $1$. All students have distinct IDs. They will be assigned to $n$ positions, and then play according to a bracket like the one below:  The figure above shows the bracket when $n=8$. To attract more students to participate, the prizes are very generous. A player eliminated in round $i$ will receive $a_i$ yuan, and the champion will receive the highest prize $a_{k+1}$ yuan. Clearly, the prizes satisfy $a_1

This is an output-only problem. All input files `match*.in` are provided in the additional files. The first line of `match*.in` contains a positive integer $n$, the total number of participants. The data guarantees that there exists a non-negative integer $k$ such that $2^k=n$. Next come $n$ lines, each containing $n$ real numbers between $0$ and $1$, $P_{i,j}$, meaning the probability that player with ID $i$ defeats player with ID $j$. Each real number is given to two digits after the decimal point. Note in particular that $P_{i,i}=0.00$. Next come $k+1$ lines, each containing one integer, giving the prizes for different rounds of advancement. The value on line $i$ is $a_i$.

The output file `match*.out` contains $n$ lines. The number on line $i$ is the ID of the student placed at position $i$. Student Z’s ID must be placed at position $1$.

#### Sample Explanation After the first round, the probability that the player with ID $1$ (Student Z) advances is $80\%$, the probability that the player with ID $2$ advances is $60\%$, the probability that the player with ID $3$ advances is $40\%$, and the probability that the player with ID $4$ advances is $20\%$. In the second round (the final), the probability that player $1$ (Student Z) wins both rounds is $80\%\times (60\%\times 70\%+40\%\times 60\%)=52.8\%$. Therefore, the probability that Student Z loses in the first round is $P_1=1-0.8=0.2$, the probability that he wins the first round but loses in the second round is $P_2=0.8-0.528=0.272$, and the probability that he becomes the champion is $P_3=0.528$. Thus, the expected prize is $0.2\times 1+(0.8-0.528)\times 2+0.528\times 3=2.328$. #### How to Test Your Output We provide `checker` to test whether your output file is acceptable. After calling this program, `checker` will give the result based on your output file, including: - Abnormal termination: unknown error. - `Format error`: output file format error. - `Not a permutation`: the output file is not a permutation of $1\sim n$. - `OK.Your answer is xxx`: the output file is accepted, and `xxx` is the corresponding expected prize. #### Scoring Method Each test point is scored independently. For each test point, if your output file is invalid (such as wrong format, or the output does not meet the requirements), you get $0$ points for that test point. Otherwise, let your expected prize be $\text{your\_ans}$, and the reference expected prize be $\text{our\_ans}$. We also have a scoring parameter $d$. Your score for that test point is as follows: - If $\text{your\_ans}>\text{our\_ans}$, you get $12$ points. - If $\text{your\_ans}