D - きんいろクッキー
Editorial
/
高橋くんのお仕事は、クッキー工場で金色のクッキーをクリックするだけの簡単なお仕事である。
クッキー工場は次の性質を持っている。
となる。
高橋君は皮算用が好きである。0 秒からはじめて、出現する金色のクッキーをすべて出現時にクリックした場合、
T-1 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を求めよ。
入力は以下の形式で標準入力から与えられる。
T-1 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を1行で出力せよ。
なお、出力の最後には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-3} 以下であれば許容される。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
クッキー工場は次の性質を持っている。
- 通常のクッキーと金色のクッキーが生成される。生成される時刻は整数秒である。
- 通常のクッキーは 1 秒につき 1 枚だけ生成される。
- 金色のクッキーは、通常のクッキーの生成条件とは別に 1 秒につき確率 P で 1 枚だけ出現する。
- クリックされた金色のクッキーは消滅し、N 通りの効果のうち 1 個の効果をもたらす。
- 効果 i は確率 q_i で起こり、その次の秒に生成される通常のクッキーから t_i 回、生成される通常のクッキーの個数を x_i 倍する。
- 上記の効果は重複する。たとえば、ある秒で効果 i が 2 回、効果 j が 1 回継続している場合、その秒でのクッキーの生成数は x_i^2*x_j 個となる。
秒 | 0 | 1 | 2 | 3 | 4 | 5 |
枚数 | 1 | 2 | 6 | 2 | 1 | 1 |
高橋君は皮算用が好きである。0 秒からはじめて、出現する金色のクッキーをすべて出現時にクリックした場合、
T-1 秒目のクッキー生成が終わった時点で、生成された通常のクッキーの総数の期待値を求めよ。
入力
T N P q_1 x_1 t_1 q_2 x_2 t_2 : q_N x_N t_N
- 1 行目は、クッキーを生成する時間を表す整数 T\ (1≦T≦100,000)、クッキーが持つ効果の種類を表す整数 N\ (1≦N≦10,000)、金色のクッキーが出現する確率 P\ (0≦P≦1) が半角空白区切りで与えられる。
- 2 行目から N 行は、金色のクッキーをクリックすることで起こる i 番目の効果を表す。その効果が表れる確率 q_i\ (0≦q_i≦1)、その効果の倍率を表す整数 x_i\ (1≦x_i≦1,000)、その効果の持続時間を表す整数 t_i\ (1≦t_i≦100,000) が、スペース区切りで与えられる。
- q_i の和は 1 となる。
- 正しい出力が 10^{100} を上回ることはない。
- 与えられる小数の入力は全て、多くても小数第 6 位までしか存在しない。
出力
なお、出力の最後には改行をいれること。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-3} 以下であれば許容される。
入力例 1
10 2 0.5 0.5 10 1 0.5 2 1
出力例 1
32.5
- 最初の 1 秒は、必ず 1 枚のクッキーが生成されます。
- 2 秒目からは、10 枚のクッキーが生成される確率が 25%、2 枚のクッキーが生成される確率が25%なので、平均して毎秒 3.5 枚のクッキーが生成されます。
入力例 2
100000 3 0.01 0.48175 7 77 0.033325 777 13 0.484925 1 100
出力例 2
16540797.4844572
入力例 3
300 1 1 1 2 1000
出力例 3
2037035976334490000000000000000000000000000000000000000000000000000000000000000000000000000
- 出力は指数表記にしてはいけません。誤差が許容される点にも注意してください。