分数: 1000 点
问题陈述
有 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 球一粒一粒地落入洞中。当球滚过洞时,如果洞中还没有球,球就会落入洞中。否则,球就会通过这个洞并继续滚动。 (在此问题中考虑的任何情况下,球永远不会碰撞。)
在每一步中,我们都会随机均匀地选择剩下的一个球,然后均匀地随机选择一个方向(左或右),并朝这个方向推动球。请计算在此过程中所有球滚动的预计总距离。
例如,当 N = 3, d_1 = 1,和 x = 1,以下是一种可能的情况:
- 第一步:推编号球 2 在它的左边,它会掉进编号为 2。滚动的距离为 3.
- 第二步:推编号球 1 在其右侧,它将通过编号为 2 并落入编号为 3。滚动的距离为 9.
- 第三步:推球编号 3 在它的右边,它会掉进编号为 4。滚动的距离为 6.
所以这个场景中的总距离是 18.
请注意,在所有情况下,每个球都会落入某个洞中,并且最终会出现一个没有球的洞。
约束
- 1 \leq N \leq 200,000
- 1 \leq d_1 \leq 100
- 0 \leq x \leq 100
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N d_1 x
输出
打印一个表示答案的浮点数。你的答案的相对或绝对误差不应高于 10^{-9}.
示例输入 1
1 3 3
示例输出 1
4.500000000000000
唯一球与左洞之间的距离为 3 唯一的球和右洞之间的距离是 6。只有两种情况(即向左推和向右推)。唯一的球会滚动 分别为 3 和 6 单位距离。所以这个例子的答案是 (3+6)/2 = 4.5.
示例输入 2
2 1 0
示例输出 2
2.500000000000000
示例输入 3
1000 100 100
示例输出 3
649620280.957660079002380