← 返回题目列表

AtCoder · agc007_c

C. 推球

中文机器翻译题面 查看原题

分数: 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,以下是一种可能的情况:

c9264131788434ac062635a675a785e3.jpg
  • 第一步:推编号球 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