結果

問題 No.76 回数の期待値で練習
ユーザー koyoprokoyopro
提出日時 2020-02-12 23:47:44
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 430 ms / 5,000 ms
コード長 1,850 bytes
コンパイル時間 1,483 ms
コンパイル使用メモリ 157,584 KB
実行使用メモリ 13,260 KB
最終ジャッジ日時 2024-10-04 07:02:26
合計ジャッジ時間 2,265 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
13,260 KB
testcase_01 AC 430 ms
13,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define array2(type, x, y) array<array<type, y>, x>
#define vector2(type) vector<vector<type> >
#define out(...) printf(__VA_ARGS__)

int dxy[] = {0, 1, 0, -1, 0};

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

#define SIZE 1234560

int N,K;
double _DP[SIZE], *DP;
double P[7] = {
    1.0/6,
    0.083333333333333,
    0.166666666666667,
    0.250000000000000,
    0.083333333333333,
    0.250000000000000,
    0.166666666666667
};
double A[7] = {
    0,
    1.0000000000000000,
    1.0833333333333333,
    1.2569444444444444,
    1.5353009259259260,
    1.6915991512345676,
    2.0513639724794235
};

void update() {
    REP(i,SIZE) _DP[i]=0;
    P[6] = 1.0;
    FOR(i,1,6) P[6]-=P[i];
    REP(_i,K) {
        int i = _i+1;
        REP(_j,6) {
            int j = _j+1;
            DP[i] += DP[i-j]*P[j];
        }
        DP[i] += 1;
    }
}
int T;

void solve() {
    K=7;
    DP = _DP+10;
#if DEBUG
    FOR(d,1,6) {
        double l = 0;
        double r = 2.0/6;
        REP(i,100) {
            P[d] = (l+r)/2;
            update();
            if (DP[d+1] > A[d+1]) r = P[d];
            else l = P[d];
        }
    }
    REP(i,6) {
        out("%.15f,\n", P[i+1]);
    }
#endif
    cin>>T;
    while(T--) {
        cin>>K;
        update();
        out("%.15f\n", DP[K]);
    }
}
0