Football

Time limit1sMemory limit128 MB

Summary

Given pairwise win probabilities, find the team most likely to win a fixed single-elimination bracket of 2^n teams.

Level: Medium5 of 10
Topics: Dynamic programming, Probability, Math
Solved: No attempts yet

Problem

Consider a single-elimination football tournament with $2^n$ teams, numbered $1, 2, \ldots, 2^n$ . In each round, all teams still in the tournament are listed in order of increasing number. Then the first team plays the second, the third plays the fourth, and so on. The winner of each match advances to the next round and the loser is eliminated. After $n$ rounds, exactly one undefeated team remains; that team is the champion.

You are given a matrix $P = [p_{ij}]$ , where $p_{ij}$ is the probability that team $i$ beats team $j$ in a single match. Determine which team is most likely to win the tournament.

Input

The input contains several test cases. Each test case begins with a line containing a single integer $n$ ( $1 \le n \le 7$ ). The next $2^n$ lines each contain $2^n$ real numbers; the $j$ -th number on the $i$ -th line is $p_{ij}$ . The matrix satisfies $p_{ij} = 1.0 - p_{ji}$ for all $i \ne j$ and $p_{ii} = 0.0$ for all $i$ . A line containing a single $-1$ marks the end of the input.

Every matrix entry is a floating-point number; use double precision to avoid rounding errors.

Output

For each test case, print a single line containing the number of the team most likely to win the tournament. It is guaranteed that the tournament-win probabilities of the two most likely teams differ by at least $0.01$ .

Hint

Consider the four-team example ( $n = 2$ ) given by the first test case. In the first round team 1 plays team 2 and team 3 plays team 4; the two winners meet in the final. The probability that team 2 wins the tournament is

$p_{21}\,p_{34}\,p_{23} + p_{21}\,p_{43}\,p_{24} = 0.9 \cdot 0.6 \cdot 0.4 + 0.9 \cdot 0.4 \cdot 0.5 = 0.396.$

The next most likely champion is team 3, with probability $0.372$ .

Examples4

Example 1

Input

2
0.0 0.1 0.2 0.3
0.9 0.0 0.4 0.5
0.8 0.6 0.0 0.6
0.7 0.5 0.4 0.0
-1

Expected output

Example 2
Input
```
1
0.0 0.3
0.7 0.0
-1
```
Expected output
```
2
```
Example 3
Input
```
1
0.0 0.9
0.1 0.0
-1
```
Expected output
```
1
```

Example 4

Input

2
0.0 0.1 0.2 0.3
0.9 0.0 0.4 0.5
0.8 0.6 0.0 0.6
0.7 0.5 0.4 0.0
1
0.0 0.8
0.2 0.0
-1

Expected output

2
1