← 返回 google 的题目列表Tournament Champion Probability
类型：online_judge
Given a fixed single-elimination tournament bracket with N = 2^n teams, numbered from 0 to N - 1, the initial order of team IDs defines their positions in the bracket:
In round 1, teams 0 and 1 play, teams 2 and 3 play, and so on.
In every subsequent round, the winners of two adjacent bracket regions play each other.
The tournament continues until one champion remains.
You are given a probability matrix P, where P[i][j] is the probability that team i beats team j in a single match. Results of different matches are independent.
Compute the probability that a specified team t wins the tournament.
Input Format
The first line contains two integers, N and t.
N is a power of two.
0 <= t < N.
The next N lines each contain N floating-point values. The j-th value on row i is P[i][j].
It is guaranteed that:
P[i][i] = 0;
0 <= P[i][j] <= 1 for i != j;
P[i][j] + P[j][i] = 1 for i != j.
Output Format
Print the probability that team t becomes champion. An absolute error of at most 1e-9 is accepted.
Example
Input:
4 0
0 0.6 0.5 0.4
0.4 0 0.7 0.8
0.5 0.3 0 0.55
0.6 0.2 0.45 0
Output:
0.2730000000
Example
Input
2 0
0 0.7
0.3 0
Output
0.7000000000