No.66 輝け☆全国たこやき杯

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下
タグ : / 解いたユーザー数 81
作問者 : なおなお
1 ProblemId : 93 / 出題時の順位表

問題文

太郎君は、「輝け☆全国たこやき杯」に参加することになりました。

この大会は、総勢\(2^M\)人の選手が出場し、
トーナメント形式で戦い、勝った選手がさらに勝ち残った選手と戦う方式で
優勝者を決定するものになっています。

\(2^M\)人の選手にはそれぞれ、\(N_1 ~ N_{2^M}\)までの選手番号が割り当てられており、
太郎君には\(N_1\)番が割り当てられました。

\(M = 3\)の例:

トーナメントの\(1\)回戦では、\(N_{2j-1}\)の選手と\(N_{2j}\)の選手が戦います。 \((1 \leq j \leq 2^{M-1})\)
そして、そのそれぞれの勝者を \(N'_j \) とし、
次の\(2\)回戦では、\(N'_{2k-1}\)の選手と\(N'_{2k}\)の選手が戦うといったように、\((1 \leq k \leq 2^{M-2})\)
合計で\(M\)回戦行うことにより、\(1\)人の優勝者が決まります。

\(2^M\)人の選手はそれぞれ、強さパラメータ\(S_i\)を持っており、
とある\(A\)選手と\(B\)選手が勝負するとき、それぞれの強さパラメータを \(S_a, S_b\) とすると
\(A\)選手が勝つ確率は \(P_a = {S_a}^2 / ({S_a}^2+{S_b}^2) \)、 \(B\)選手が勝つ確率は \(P_b = {S_b}^2 / ({S_a}^2+{S_b}^2) \)
で表されます。
選手ごとの相性など、上記以外の要素は勝敗に影響されません。

入力に\(2^M\)人の選手の強さパラメータが与えられるので、
太郎君が優勝する確率を求めてください。

入力

\(M\)
\(S_1\)
\(S_2\)
\(\dots\)
\(S_i\)
\(\dots\)
\(S_{2^M}\)

\(1\)行目に、選手の人数\((2^M)\)を表す\(M\ (1 \leq M \leq 10)\) が与えられます。
続く\(2^M\)行に、各選手の強さパラメータを表す\(S_i\ (1 \leq S_i \leq 30000, 1 \leq i \leq 2^M)\)が与えられます。

出力

太郎君が優勝する確率を、\(0\)から\(1\)の範囲の小数で出力してください。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が \(10^{−6}\) 以下であれば許容されます。
最後に改行してください。

サンプル

サンプル1
入力
2
1
2
3
4
出力
0.0147294

\(1\)回戦では、太郎君\(N_1\)(強さ\(1\))と選手\(N_2\)(強さ\(2\))が戦います。
太郎君\(N_1\)が勝つ確率は \(1^2 / (1^2+2^2) = 0.2\)、
選手\(N_2\)が勝つ確率は \(2^2 / (1^2+2^2) = 0.8\)、となります。
同様に、選手\(N_3\)(強さ\(3\))と選手\(N_4\)(強さ\(4\))が戦い、
選手\(N_3\)が勝つ確率は \(3^2 / (3^2+4^2) = 0.36\)、
選手\(N_4\)が勝つ確率は \(4^2 / (3^2+4^2) = 0.64\)、となります。

次に\(2\)回戦では太郎君の相手は、選手\(N_3\)または選手\(N_4\)の勝った方と戦います。
太郎君と選手\(N_3\)が勝負したとき、太郎君が勝つ確率は \(1^2 / (1^2+3^2) = 0.1\)、
太郎君と選手\(N_4\)が勝負したとき、太郎君が勝つ確率は \(1^2 / (1^2+4^2) = 0.0588235\) となるので、
太郎君が\(2\)回戦に勝つ確率は \(0.36 \times 0.1 + 0.64 \times 0.0588235 = 0.0736467\)
これに、太郎君が\(1\)回戦を勝ち抜く確率 \(0.2\) を掛けて\(0.0147294\)が、太郎君が優勝する確率となります。

サンプル2
入力
1
3000
2995
出力
0.5008340

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。