题目描述

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

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

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

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

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

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

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

输入格式

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

$N$ $d_1$ $x$

输出格式

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

题目大意

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

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

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

给定 $N, d_1, x$ ，求出在不发生碰撞的情况下，每个球移动距离的期望（误差小于 $10^{-9}$）。

1 3 3

4.500000000000000

2 1 0

2.500000000000000

1000 100 100

649620280.957660079002380

提示

制約

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

Sample Explanation 1

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