atcoder#AGC007C. [AGC007C] Pushing Balls

[AGC007C] Pushing Balls

题目描述

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

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

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

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

c9264131788434ac062635a675a785e3.jpg

  1. 2 2 番の球を左に転がす。球は 2 2 番の穴に落ちる。球が移動する距離は 3 3 である。
  2. 1 1 番の球を右に転がす。球は 2 2 番の穴の上を通り、3 3 番の穴に落ちる。球が移動する距離は 9 9 である。
  3. 3 3 番の球を右に転がす。球は 4 4 番の穴に落ちる。球が移動する距離は 6 6 である。

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

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

输入格式

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

N N d1 d_1 x x

输出格式

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

题目大意

在一条直线上有 NN 个球和 N+1N+1 个洞。记每个球与相邻的洞的距离为 di(1i2×N)d_i \left( 1 \leq i \leq 2 \times N \right)di+1di=xd_{i + 1} - d_i = x

要将 NN 个球均推入洞中。当球滚过洞时,如果洞中还没有球,球将掉入洞中。否则,球将继续滚动。

每次会随机选择任一未进洞的球,并随机选择一个方向推球。

给定 N,d1,xN, d_1, x ,求出在不发生碰撞的情况下,每个球移动距离的期望(误差小于 10910^{-9})。

1 3 3
4.500000000000000
2 1 0
2.500000000000000
1000 100 100
649620280.957660079002380

提示

制約

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

Sample Explanation 1

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