#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int INF = 1e9; const ll LINF = 1e18; template ostream& operator << (ostream& out,const pair& o){ out << "(" << o.first << "," << o.second << ")"; return out; } template ostream& operator << (ostream& out,const vector V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; } template ostream& operator << (ostream& out,const vector > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; } template ostream& operator << (ostream& out,const map mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; } /* 問題文============================================================ 太郎君は、「輝け☆全国たこやき杯」に参加することになりました。 この大会は、総勢2M人の選手が出場し、 トーナメント形式で戦い、勝った選手がさらに勝ち残った選手と戦う方式で 優勝者を決定するものになっています。 2^M人の選手にはそれぞれ、N1~N2Mまでの選手番号が割り当てられており、 太郎君にはN1番が割り当てられました。 トーナメントの1回戦では、N_2j−1の選手とN2jの選手が戦います。 (1≤j≤2^M−1) そして、そのそれぞれの勝者を N′_j とし、 次の2回戦では、N′_2k−1の選手とN′_2kの選手が戦うといったように、(1≤k≤2^M−2) 合計でM回戦行うことにより、1人の優勝者が決まります。 2M人の選手はそれぞれ、強さパラメータSiを持っており、 とあるA選手とB選手が勝負するとき、それぞれの強さパラメータを Sa,Sb とすると A選手が勝つ確率は Pa=Sa^2/(Sa^2+Sb^2)、 B選手が勝つ確率は Pb=Sb^2/(Sa^2+Sb^2) で表されます。 選手ごとの相性など、上記以外の要素は勝敗に影響されません。 入力に2^M人の選手の強さパラメータが与えられるので、 太郎君が優勝する確率を求めてください。 ================================================================= 解説============================================================= 0 1 10 11 ================================================================ */ typedef long double ld; ld solve(){ ld res = 0.; ll M; cin >> M; vector S(1<> in; vector> dp(M+1,vector(1<(S1) << " " << bitset<16>(S2) << endl; // cout << "=========" << endl; for(int j = 0; j < (1<(j&(~S2)) << " " << bitset<16>(j|(S2)) << endl; // cout << bitset<16>(j&(~S1)) << " " << bitset<16>(j|S1) << endl; int battlel = j&(~S1),battler = j|S1; int nbattlel = j&(~S2),nbattler = j|S2; for(int k = battlel; k <= battler; k++){ if(nbattlel <= k && k <= nbattler) continue; dp[i][j] += dp[i-1][j]*dp[i-1][k]*(S[j]*S[j]/(S[j]*S[j]+S[k]*S[k])); } } } res = dp[M][0]; return res; } int main(void) { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(12) << solve() << endl; return 0; }