結果

問題 No.76 回数の期待値で練習
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-04-28 22:46:35
言語 Python2
(2.7.18)
結果
AC  
実行時間 2,005 ms / 5,000 ms
コード長 1,137 bytes
コンパイル時間 40 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 38,272 KB
最終ジャッジ日時 2024-07-05 05:06:50
合計ジャッジ時間 6,431 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,003 ms
38,012 KB
testcase_01 AC 2,005 ms
38,272 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
N = int(1e6)
E = [0, 1., 1.0833333333333333, 1.2569444444444444, 1.5353009259259260, 1.6915991512345676, 2.0513639724794235] + [0] * N
p = [0] * 7
# 1 + p1
p[1] = E[2] - 1
# 1 + p1**2 + p1 + p2
p[2] = E[3] - p[1] - p[1]**2 - 1
# 1 + p1**3 + p1**2 + 2p1p2 + p1 + p2 + p3
p[3] = E[4] - p[1] - p[1]**2 - p[1]**3 - 2*p[1]*p[2] - p[2] - 1
# 1 + p1**4 + p1**3 + 3(p1**2)p2 + p1**2 + p2**2 + 2p1p2 + 2p1p3 + p1 + p2 + p3 + p4
p[4] = E[5] - p[1]**4 - p[1]**3 - 3*(p[1]**2)*p[2] - p[1]**2 - p[1] - 2*p[1]*p[2] - p[2]**2 - 2*p[1]*p[3] - p[2] - p[3] - 1
# 1 + p1**5 + p1**4 + 4(p1**3)p2 + 3(p1**2)p2 + 3(p1**2)p3 + 3p1(p2**2) + p1**3 + p1**2 + p2**2 + 2p1p4 + 2p1p2 + 2p1p3 + 2p2p3 + p1 + p2 + p3 + p4 + p5
p[5] = E[6] - p[1]**5 - p[1]**4 - 4*(p[1]**3)*p[2] - p[1]**3 - 3*(p[1]**2)*p[2] - 3*(p[1]**2)*p[3] - 3*p[1]*(p[2]**2) - p[1]**2 - p[2]**2 - 2*p[1]*p[2] - 2*p[2]*p[3] - 2*p[1]*p[4] - 2*p[1]*p[3] - p[1] - p[2] - p[3] - p[4] - 1
p[6] = 1 - sum(p[:6])

for x in xrange(7, N+1):
    E[x] = 1
    for i in xrange(6):
        E[x] += E[x-i-1]*p[i+1]
t = int(raw_input())
for _ in xrange(t):
    n = int(raw_input())
    print E[n]
0