結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー hogeover30
提出日時 2015-02-05 04:16:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,208 ms / 5,000 ms
コード長 1,056 bytes
コンパイル時間 540 ms
コンパイル使用メモリ 67,100 KB
実行使用メモリ 89,580 KB
最終ジャッジ日時 2024-06-23 08:24:54
合計ジャッジ時間 2,117 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

double memo[1000010], p[7];
double E[7]={
    1, 1.0000000000000000, 1.0833333333333333, 1.2569444444444444,
    1.5353009259259260, 1.6915991512345676, 2.0513639724794235
};
double f(int x, int k)
{
    if (x>=k) return 0;
    double& res=memo[x];
    if (res>0) return res;
    res=1;
    for(int i=1;i<=6;++i) res+=f(x+i, k)*p[i];
    return res;
}
double f2(int x, int k)
{
    if (x>=k) return 0;
    double res=1;
    for(int i=1;i<=6;++i) res+=f2(x+i, k)*p[i];
    return res;
}
void getProb()
{
    double q=0;
    for(int i=1;i<=5;++i) {
        double l=0, r=1-q;
        for(int $=0;$<30;++$) {
            double m=(l+r)*.5;
            p[i]=m;
            if (f2(0, i+1)<E[i+1])
                l=m;
            else
                r=m;
        }
        q+=p[i];
    }
    p[6]=1-q;
}
int main()
{
    getProb();
    int T; cin>>T;
    while (T--) {
        int n; cin>>n;
        fill(memo, memo+n, 0);
        cout<<setprecision(20)<<f(0, n)<<endl;
    }
}
0