atcoder#AGC007C. [AGC007C] Pushing Balls

[AGC007C] Pushing Balls

配点 : 10001000

問題文

NN 個の球と N+1N+1 個の穴が一直線上に並んでいます。球には左から順に 11 から NN の番号が、穴には左から順に 11 から N+1N+1 の番号が振られています。ii 番の球は ii 番の穴と i+1i+1 番の穴の間に置かれており、隣り合う穴と球の間の距離を左から順に並べて得られる数列を did_i (1i2×N1 \leq i \leq 2 \times N) とおきます。d1d_1 の値とパラメータ xx が与えられており、didi1=xd_i - d_{i-1} = x が任意の ii (2i2×N2 \leq i \leq 2 \times N) に対して成り立っています。

これら NN 個の球を 11 個ずつ転がし、穴に落としていくことを考えます。球が穴の上を通ると、その穴にすでに別の球が入っていなければその穴に落ちます。すでに別の球がその穴に入っていた場合は、球は落ちずにそのまま転がり続けます。(なお、この問題で考える球の転がし方において、球どうしが衝突することはありません。)

球を転がす際は、まだ転がされていない球の中から等確率で 11 つを選び、その球を左または右に等確率で転がします。これを NN 回繰り返してすべての球を転がすとき、すべての球が移動する距離の総和の期待値を求めてください。

以下に N=3N = 3, d1=1d_1 = 1, x=1x = 1 の場合の球の転がし方の例を挙げます。

c9264131788434ac062635a675a785e3.jpg

  1. 22 番の球を左に転がす。球は 22 番の穴に落ちる。球が移動する距離は 33 である。
  2. 11 番の球を右に転がす。球は 22 番の穴の上を通り、33 番の穴に落ちる。球が移動する距離は 99 である。
  3. 33 番の球を右に転がす。球は 44 番の穴に落ちる。球が移動する距離は 66 である。

この例では、球が移動する距離の総和は 1818 となります。

なお、球をどのように転がしてもどの球も必ずいずれかの穴に落ち、最後に穴が一つだけ空のまま残ることになります。

制約

  • 1N200,0001 \leq N \leq 200,000
  • 1d11001 \leq d_1 \leq 100
  • 0x1000 \leq x \leq 100
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN d1d_1 xx

出力

答えを小数で出力せよ。絶対誤差または相対誤差のいずれかが 10910^{-9} 以内でなければならない。

1 3 3
4.500000000000000

球が 11 個、穴が 22 個あります。球から左の穴までの距離は 33 、球から右の穴までの距離は 66 です。球を左に転がすか右に転がすかの 22 通りの転がし方があり、それぞれにおいて球が移動する距離は 3,63, 6 です。したがって、答えは (3+6)/2=4.5(3+6)/2 = 4.5 となります。

2 1 0
2.500000000000000
1000 100 100
649620280.957660079002380