結果

問題 No.76 回数の期待値で練習
コンテスト
ユーザー data9824
提出日時 2015-06-07 02:43:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 598 ms / 5,000 ms
コード長 1,056 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 69,008 KB
実行使用メモリ 18,356 KB
最終ジャッジ日時 2024-07-06 14:33:35
合計ジャッジ時間 1,546 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>

using namespace std;

const double EX[7] = {
	-1,
	1.0000000000000000,
	1.0833333333333333,
	1.2569444444444444,
	1.5353009259259260,
	1.6915991512345676,
	2.0513639724794235
};
vector<double> p(7);

double expected(int n) {
	if (n <= 6) {
		return EX[n];
	}
	vector<double> count(n + 1);
	for (int i = 1; i <= 6; ++i) {
		count[i] = EX[i];
	}
	for (int i = 7; i <= n; ++i) {
		count[i] = 0.0;
		for (int k = 1; k <= 6; ++k) {
			count[i] += (1.0 + count[i - k]) * p[k];
		}
	}
	return count[n];
}

int main() {
	p[1] = EX[2] - 1.0;
	p[2] = EX[3] - EX[2] * p[1] - 1.0;
	p[3] = EX[4] - EX[3] * p[1] - EX[2] * p[2] - 1.0;
	p[4] = EX[5] - EX[4] * p[1] - EX[3] * p[2] - EX[2] * p[3] - 1.0;
	p[5] = EX[6] - EX[5] * p[1] - EX[4] * p[2] - EX[3] * p[3] - EX[2] * p[4] - 1.0;
	p[6] = 1.0 - accumulate(&p[1], &p[5] + 1, 0.0);
	int t;
	cin >> t;
	vector<int> n(t);
	for (int i = 0; i < t; ++i) {
		cin >> n[i];
		cout << fixed << setprecision(10) << expected(n[i]) << endl;
	}
	return 0;
}
0