結果

問題 No.76 回数の期待値で練習
ユーザー pekempeypekempey
提出日時 2015-08-20 10:53:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 67 ms / 5,000 ms
コード長 1,203 bytes
コンパイル時間 2,299 ms
コンパイル使用メモリ 157,944 KB
実行使用メモリ 69,132 KB
最終ジャッジ日時 2024-07-18 10:49:54
合計ジャッジ時間 1,760 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,472 KB
testcase_01 AC 67 ms
69,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;
const ll inf = 1e9;
const ll mod = 1e9 + 7;

double P[7];
double dp[1010101];

double E(int n) {
	if (n <= 0) return 0;	
	if (dp[n] >= 0) return dp[n];
	double res = 0;
	for (int i = 1; i <= 6; i++) {
		res += P[i] * (E(n - i) + 1);
	}
	return dp[n] = res;
}

int main() {
	int T;
	cin >> T;

	rep (i, 1010101) dp[i] = -1;
	dp[1] = 1.0000000000000000;
	dp[2] = 1.0833333333333333;
	dp[3] = 1.2569444444444444;
	dp[4] = 1.5353009259259260;
	dp[5] = 1.6915991512345676;
	dp[6] = 2.0513639724794235;

	P[1] = (dp[2] - 1) / dp[1];
	P[2] = (dp[3] - P[1] * dp[2] - 1) / dp[1];
	P[3] = (dp[4] - P[1] * dp[3] - P[2] * dp[2] - 1) / dp[1];
	P[4] = (dp[5] - P[1] * dp[4] - P[2] * dp[3] - P[3] * dp[2] - 1) / dp[1];
	P[5] = (dp[6] - P[1] * dp[5] - P[2] * dp[4] - P[3] * dp[3] - P[4] * dp[2] - 1) / dp[1];
	P[6] = 1 - P[1] - P[2] - P[3] - P[4] - P[5];

	while (T--) {
		int N;
		cin >> N;
		printf("%.20f\n", E(N));
	}

	return 0;
}
0