結果
問題 |
No.66 輝け☆全国たこやき杯
|
ユーザー |
![]() |
提出日時 | 2014-11-14 20:35:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,048 bytes |
コンパイル時間 | 667 ms |
コンパイル使用メモリ | 55,808 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-31 10:51:31 |
合計ジャッジ時間 | 1,424 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <iostream> #include <cstdio> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,j) int M; double S[1024], dp[11][1024]; bool calculated[11][1024]; // indexがstageで勝つ確率(l, rはどこまでか) double rec(int index, int stage, int l, int r){ if(stage == M){return 1.0f;} if(calculated[stage][index]){return dp[stage][index];} int mid = (l+r) / 2; double res = 0.0f; if(l <= index && index < mid){ FOR(i, mid, r){ res += rec(i, stage+1, mid, r) * S[index] / (S[index] + S[i]); } res *= rec(index, stage+1, l, mid); }else{ FOR(i, l, mid){ res += rec(i, stage+1, l, mid) * S[index] / (S[index] + S[i]); } res *= rec(index, stage+1, mid, r); } calculated[stage][index] = true; return dp[stage][index] = res; } int main(){ std::cin >> M; REP(i, 1<<M){ std::cin >> S[i]; S[i] *= S[i]; } printf("%.8f\n", rec(0, 0, 0, 1<<M)); }