結果

問題 No.76 回数の期待値で練習
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-04-28 18:29:54
言語 Python2
(2.7.18)
結果
AC  
実行時間 1,506 ms / 5,000 ms
コード長 1,361 bytes
コンパイル時間 76 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 39,888 KB
最終ジャッジ日時 2024-07-05 05:02:38
合計ジャッジ時間 5,221 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,506 ms
39,888 KB
testcase_01 AC 1,496 ms
39,832 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
from fractions import Fraction
E = map(lambda x: x.limit_denominator(), [Fraction('1.0000000000000000'), Fraction('1.0833333333333333'), Fraction('1.2569444444444444'), Fraction('1.5353009259259260'), Fraction('1.6915991512345676'), Fraction('2.0513639724794235')])
p = [0] * 7
# 1 + p1
p[1] = E[1] - E[0]
# 1 + p1**2 + p1 + p2
p[2] = E[2] - p[1] - p[1]**2 - E[0]
# 1 + p1**3 + p1**2 + 2p1p2 + p1 + p2 + p3
p[3] = E[3] - p[1] - p[1]**2 - p[1]**3 - 2*p[1]*p[2] - p[2] - E[0]
# 1 + p1**4 + p1**3 + 3(p1**2)p2 + p1**2 + p2**2 + 2p1p2 + 2p1p3 + p1 + p2 + p3 + p4
p[4] = E[4] - 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] - E[0]
# 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[5] - 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] - E[0]
p[6] = 1 - sum(p[:6])

p = map(float, p)

N = int(1e6)
dp = [0] * (N-6) + E[::-1] + [0]
for x in reversed(xrange(N-6)):
    dp[x] = 1 + sum(dp[x+i]*p[i] for i in xrange(1, 7))
t = int(raw_input())
print '\n'.join(map(str, (float(dp[-1-int(raw_input())]) for _ in xrange(t))))
0