atcoder#AGC007C. [AGC007C] Pushing Balls
[AGC007C] Pushing Balls
配点 : 点
問題文
個の球と 個の穴が一直線上に並んでいます。球には左から順に から の番号が、穴には左から順に から の番号が振られています。 番の球は 番の穴と 番の穴の間に置かれており、隣り合う穴と球の間の距離を左から順に並べて得られる数列を () とおきます。 の値とパラメータ が与えられており、 が任意の () に対して成り立っています。
これら 個の球を 個ずつ転がし、穴に落としていくことを考えます。球が穴の上を通ると、その穴にすでに別の球が入っていなければその穴に落ちます。すでに別の球がその穴に入っていた場合は、球は落ちずにそのまま転がり続けます。(なお、この問題で考える球の転がし方において、球どうしが衝突することはありません。)
球を転がす際は、まだ転がされていない球の中から等確率で つを選び、その球を左または右に等確率で転がします。これを 回繰り返してすべての球を転がすとき、すべての球が移動する距離の総和の期待値を求めてください。
以下に , , の場合の球の転がし方の例を挙げます。
- 番の球を左に転がす。球は 番の穴に落ちる。球が移動する距離は である。
- 番の球を右に転がす。球は 番の穴の上を通り、 番の穴に落ちる。球が移動する距離は である。
- 番の球を右に転がす。球は 番の穴に落ちる。球が移動する距離は である。
この例では、球が移動する距離の総和は となります。
なお、球をどのように転がしてもどの球も必ずいずれかの穴に落ち、最後に穴が一つだけ空のまま残ることになります。
制約
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを小数で出力せよ。絶対誤差または相対誤差のいずれかが 以内でなければならない。
1 3 3
4.500000000000000
球が 個、穴が 個あります。球から左の穴までの距離は 、球から右の穴までの距離は です。球を左に転がすか右に転がすかの 通りの転がし方があり、それぞれにおいて球が移動する距離は です。したがって、答えは となります。
2 1 0
2.500000000000000
1000 100 100
649620280.957660079002380