結果
問題 | No.75 回数の期待値の問題 |
ユーザー | batsumaru |
提出日時 | 2019-09-07 00:03:57 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 336 ms / 5,000 ms |
コード長 | 860 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 167,364 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-07 03:15:22 |
合計ジャッジ時間 | 4,208 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,380 KB |
testcase_01 | AC | 5 ms
4,380 KB |
testcase_02 | AC | 8 ms
4,380 KB |
testcase_03 | AC | 14 ms
4,380 KB |
testcase_04 | AC | 9 ms
4,376 KB |
testcase_05 | AC | 11 ms
4,376 KB |
testcase_06 | AC | 12 ms
4,380 KB |
testcase_07 | AC | 15 ms
4,376 KB |
testcase_08 | AC | 18 ms
4,380 KB |
testcase_09 | AC | 19 ms
4,380 KB |
testcase_10 | AC | 21 ms
4,380 KB |
testcase_11 | AC | 23 ms
4,376 KB |
testcase_12 | AC | 24 ms
4,380 KB |
testcase_13 | AC | 26 ms
4,376 KB |
testcase_14 | AC | 28 ms
4,376 KB |
testcase_15 | AC | 35 ms
4,380 KB |
testcase_16 | AC | 144 ms
4,380 KB |
testcase_17 | AC | 259 ms
4,376 KB |
testcase_18 | AC | 312 ms
4,376 KB |
testcase_19 | AC | 336 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> typedef long long ll; using namespace std; #define DUMP(x) cout << #x << " = " << (x) << endl; #define FOR(i, m, n) for(ll i = m; i < n; i++) #define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- ) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) #define FOREACH(x,a) for(auto& (x) : (a) ) #define ALL(v) (v).begin(), (v).end() #define SZ(x) ll(x.size()) int main(){ ll K; cin >> K; double lb = 0.0, ub = 1000, m ; //dp[i] = 総和がiの状態からスタートした場合の期待値 vector<double> dp(K+6,0.0); //dp[0]を決め打ちして二分探索 REP(_,100000){ m = (lb+ub)/2.0; FOR(i,1,6) dp[K+i] = m; dp[K] = 0.0; IREP(i,K){ dp[i] = 1.0; FOR(j,1,7) dp[i] += dp[i+j]/6.0; } if(m>dp[0]) ub = m; else lb = m; } cout << fixed << setprecision(10) << m << endl; }