atcoder#AGC007C. [AGC007C] Pushing Balls

[AGC007C] Pushing Balls

Score : 10001000 points

Problem Statement

There are NN balls and N+1N+1 holes in a line. Balls are numbered 11 through NN from left to right. Holes are numbered 11 through N+1N+1 from left to right. The ii-th ball is located between the ii-th hole and (i+1)(i+1)-th hole. We denote the distance between neighboring items (one ball and one hole) from left to right as did_i (1i2×N1 \leq i \leq 2 \times N). You are given two parameters d1d_1 and xx. didi1d_i - d_{i-1} is equal to xx for all ii (2i2×N2 \leq i \leq 2 \times N).

We want to push all NN balls into holes one by one. When a ball rolls over a hole, the ball will drop into the hole if there is no ball in the hole yet. Otherwise, the ball will pass this hole and continue to roll. (In any scenario considered in this problem, balls will never collide.)

In each step, we will choose one of the remaining balls uniformly at random and then choose a direction (either left or right) uniformly at random and push the ball in this direction. Please calculate the expected total distance rolled by all balls during this process.

For example, when N=3N = 3, d1=1d_1 = 1, and x=1x = 1, the following is one possible scenario:

c9264131788434ac062635a675a785e3.jpg

  • first step: push the ball numbered 22 to its left, it will drop into the hole numbered 22. The distance rolled is 33.
  • second step: push the ball numbered 11 to its right, it will pass the hole numbered 22 and drop into the hole numbered 33. The distance rolled is 99.
  • third step: push the ball numbered 33 to its right, it will drop into the hole numbered 44. The distance rolled is 66.

So the total distance in this scenario is 1818.

Note that in all scenarios every ball will drop into some hole and there will be a hole containing no ball in the end.

Constraints

  • 1N200,0001 \leq N \leq 200,000
  • 1d11001 \leq d_1 \leq 100
  • 0x1000 \leq x \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

NN d1d_1 xx

Output

Print a floating number denoting the answer. The relative or absolute error of your answer should not be higher than 10910^{-9}.

1 3 3
4.500000000000000

The distance between the only ball and the left hole is 33 and distance between the only ball and the right hole is 66. There are only two scenarios (i.e. push left and push right). The only ball will roll 33 and 66 unit distance, respectively. So the answer for this example is (3+6)/2=4.5(3+6)/2 = 4.5.

2 1 0
2.500000000000000
1000 100 100
649620280.957660079002380