C - トーナメント 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

2^K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。
  • 第 1 ラウンドでは、1 と 2、3 と 4、…　が試合を行う。
  • 第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), …　が試合を行う。
  • 第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), …　が試合を行う。
  • 以下同様に第 K ラウンドまで行う。
第 K ラウンドの終了後に優勝者が決定する。人 i の Elo Rating が R_i であるとき、人 i の優勝確率を求めよ。

ただし、Elo Rating R_P の人 P と Elo Rating R_Q の人 Q が対戦した場合、人 P が勝つ確率は 1 / (1 + 10^{(R_Q - R_P) / 400}) であり、異なる試合の勝敗は独立であるとする。

Constraints

  • 1 ≤ K ≤ 10
  • 0 ≤ R_i ≤ 4000

Input Format

入力は以下の形式で標準入力から与えられる。
K
R_1
…
R_{2^K}

Output Format

答えを 2^K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10^{-6} 以下のとき正当と判定される。

Sample Input 1

1
2200
2600

Sample Output 1

0.090909091
0.909090909

Sample Input 2

3
2000
2500
2300
2700
2100
2400
2600
2200

Sample Output 2

0.000086893
0.122042976
0.005522752
0.493464665
0.000651695
0.053982389
0.321828438
0.002420190