結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー izuru_matsuura
提出日時 2016-09-15 21:55:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 1,712 bytes
コンパイル時間 1,573 ms
コンパイル使用メモリ 167,896 KB
実行使用メモリ 19,168 KB
最終ジャッジ日時 2024-11-17 06:13:47
合計ジャッジ時間 2,012 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        auto i = vs.begin();
        os << "[" << *i;
        for (++i; i != vs.end(); ++i) os << " " << *i;
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    double dat[] = {
        0, 
        1.0000000000000000,
        1.0833333333333333,
        1.2569444444444444,
        1.5353009259259260,
        1.6915991512345676,
        2.0513639724794235
    };

    void input() {
    }

    void solve() {
        const int N = int(1e6 + 5);
        vector<real> P(N, 0);
        vector<real> PR(7, 0);
        for (int i = 0; i < 6; i++) P[i] = dat[i + 1] - dat[i];
        for (int i = 1; i < 6; i++) {
            real r = P[i];
            for (int j = 1; j <= i; j++) {
                r -= P[j] * PR[i - j];
            }
            PR[i] = r / P[0];
        }
        PR[6] = 1;
        for (int i = 1; i <= 5; i++) PR[6] -= PR[i];

        for (int i = 6; i < N; i++) {
            for (int j = 1; j <= 6; j++) {
                P[i] += P[i - j] * PR[j];
            }
        }

        vector<real> E(N, 0);
        E[1] = 1.0;
        for (int i = 1; i < N; i++) {
            E[i + 1] = E[i] + P[i];
        }

        int T; cin >> T;
        for (int i = 0; i < T; i++) {
            int n; cin >> n;
            printf("%.12f\n", E[n]);
        }
    }
}

int main() {
    input(); solve();
    return 0;
}
0