結果

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

ソースコード

diff # 

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

double dp[1000010], p[7];
double E[7]={
    1, 1.0000000000000000, 1.0833333333333333, 1.2569444444444444,
    1.5353009259259260, 1.6915991512345676, 2.0513639724794235
};
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();
    for(int i=0;i<7;++i) dp[i]=E[i];
    int T; cin>>T;
    while (T--) {
        int n; cin>>n;
        for(int i=7;i<=n;++i) {
            dp[i]=1;
            for(int j=1;j<=6;++j) dp[i]+=dp[i-j]*p[j];
        }
        cout<<setprecision(20)<<dp[n]<<endl;
    }
}
0