結果
問題 | No.162 8020運動 |
ユーザー | tottoripaper |
提出日時 | 2015-03-28 17:10:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,305 bytes |
コンパイル時間 | 326 ms |
コンパイル使用メモリ | 42,300 KB |
実行使用メモリ | 81,924 KB |
最終ジャッジ日時 | 2023-09-11 10:49:03 |
合計ジャッジ時間 | 28,218 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 615 ms
79,532 KB |
testcase_01 | AC | 716 ms
80,688 KB |
testcase_02 | AC | 775 ms
81,308 KB |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | AC | 616 ms
79,564 KB |
testcase_10 | AC | 772 ms
81,372 KB |
testcase_11 | AC | 715 ms
80,608 KB |
testcase_12 | AC | 662 ms
80,064 KB |
testcase_13 | RE | - |
testcase_14 | AC | 629 ms
79,556 KB |
testcase_15 | AC | 627 ms
79,596 KB |
testcase_16 | AC | 672 ms
80,132 KB |
testcase_17 | AC | 638 ms
79,788 KB |
testcase_18 | AC | 820 ms
81,836 KB |
testcase_19 | AC | 766 ms
81,200 KB |
testcase_20 | AC | 785 ms
81,400 KB |
testcase_21 | AC | 785 ms
81,464 KB |
testcase_22 | AC | 775 ms
81,376 KB |
testcase_23 | AC | 782 ms
81,464 KB |
testcase_24 | AC | 767 ms
81,280 KB |
testcase_25 | AC | 794 ms
81,568 KB |
testcase_26 | AC | 615 ms
79,492 KB |
testcase_27 | AC | 729 ms
80,716 KB |
testcase_28 | AC | 820 ms
81,800 KB |
ソースコード
// Wrongri-La Shower #include <cstdio> #include <vector> typedef std::pair<int,double> Pair; double P[3]; // 虫歯に「なる」確率 std::vector<Pair> ns[1<<14]; double dp[20][1<<14]; double probability(int prev, int next){ double res = 1.0; for(int i=0;i<14;i++){ if(!(prev >> i & 1)){continue;} double p; if(i == 0){ p = P[prev >> 1 & 1]; }else if(i == 13){ p = P[prev >> 12 & 1]; }else{ p = P[(prev >> i-1 & 1) + (prev >> i+1 & 1)]; } res *= next >> i & 1 ? 1.0-p : p; } return res; } int main(){ int N; scanf("%d", &N); N = 80-N; scanf("%lf %lf %lf", P, P+1, P+2); for(int i=0;i<3;i++){P[i] /= 100;} for(int i=0;i<1<<14;i++){ for(int j=0;j<1<<14;j++){ if((i & j) != j){continue;} ns[i].push_back(std::make_pair(j, probability(i, j))); } } dp[0][(1<<14)-1] = 1.0; for(int i=0;i<N;i++){ for(int j=0;j<1<<14;j++){ for(const auto& p : ns[j]){ dp[i+1][p.first] += dp[i][j] * p.second; } } } double res = 0.0; for(int i=0;i<1<<14;i++){ res += dp[N][i] * __builtin_popcount(i); } printf("%.12f\n", res * 2); }