Under construction

Still being built. Things may change

Tournament Winner

Interview

Time limit2sMemory limit128 MB

Summary
Given all pairwise win probabilities among 8 players in a fixed single-elimination bracket, compute each player's probability of winning the whole tournament.
Level

Medium4 of 10

Topics
Probability, Dynamic programming, Simulation, Math
Solved
No attempts yet

Problem

A tournament has 8 participants and is played over 3 rounds.

In round 1, match i is played between participant 2 × i and participant 2 × i + 1 (0 ≤ i ≤ 3). The 4 winners advance to round 2.

In round 2, the winner of round-1 match 2 × i plays the winner of round-1 match 2 × i + 1 (0 ≤ i ≤ 1). The 2 winners advance to round 3.

In round 3, the two round-2 winners play each other to decide the tournament winner.

Given every head-to-head win probability among the 8 participants, compute the probability that each participant wins the tournament.

Input

The first line contains 28 integers. The first 7 values are the probabilities that participant 0 beats participants 1 through 7, respectively. The next 6 values are the probabilities that participant 1 beats participants 2 through 7, respectively. The remaining values continue in the same order: for each lower-numbered participant, the probabilities of beating each higher-numbered participant are given in increasing opponent order. Every value is an integer.

Output

Print one line containing the probability that each participant from 0 through 7 wins the tournament, separated by spaces. An absolute or relative error of at most 10^-9 is accepted.

Examples6

  1. Example 1

    Input
    5 0 10 15 20 25 30 0 35 40 45 50 55 100 100 100 100 100 60 65 70 75 80 85 90 95 50 50
    Expected output
    0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0

  2. Example 2

    Input
    100 25 0 25 25 25 25 25 25 25 25 25 25 0 25 25 25 25 50 25 25 25 100 25 100 25 25 0
    Expected output
    0.0 0.0 0.0 0.5 0.5 0.0 0.0 0.0

  3. Example 3

    Input
    50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
    Expected output
    0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125

  4. Example 4

    Input
    100 50 50 50 50 50 50 0 50 50 50 50 50 100 50 50 50 50 0 50 50 50 100 50 50 0 50 100
    Expected output
    0.25 0.0 0.25 0.0 0.25 0.0 0.25 0.0

  5. Example 5

    Input
    50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 100 100 100 10 20 30
    Expected output
    0.125 0.125 0.125 0.125 0.5 0.0 0.0 0.0

  6. Example 6

    Input
    1 2 4 7 11 16 22 3 5 8 12 17 23 6 9 13 18 24 10 14 19 25 15 20 26 21 27 28
    Expected output
    0.0000688919608 0.009061234459199999 0.011498979459599998 0.1853675541204 0.0328889066112 0.18542493028680002 0.17985791390280004 0.3958315891991999