102246: [AtCoder]ABC224 G - Roll or Increment

Problem Statement

We have a $N$-face die (singular of dice) that shows integers from $1$ through $N$ with equal probability.
Below, the die is said to be showing an integer $X$ when it is placed so that the top face is the face with the integer $X$.
Initially, the die shows the integer $S$.

You can do the following two operations on this die any number (possibly zero) of times in any order.

• Pay $A$ yen (the Japanese currency) to "increase" the value shown by the die by $1$, that is, reposition it to show $X+1$ when it currently shows $X$. This operation cannot be done when the die shows $N$.
• Pay $B$ yen to recast the die, after which it will show an integer between $1$ and $N$ with equal probability.

Consider making the die show $T$ from the initial state where it shows $S$.
Print the minimum expected value of the cost required to do so when the optimal strategy is used to minimize this expected value.

Constraints

• $1 \leq N \leq 10^9$
• $1 \leq S, T \leq N$
• $1 \leq A, B \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $S$ $T$ $A$ $B$

Output

Print the answer. Your output will be considered correct when its absolute or relative error is at most $10^{-5}$.

Sample Input 1

5 2 4 10 4

Sample Output 1

15.0000000000000000

When the optimal strategy is used to minimize the expected cost, it will be $15$ yen.

Sample Input 2

10 6 6 1 2

Sample Output 2

0.0000000000000000

The die already shows $T$ in the initial state, which means no operation is needed.

Sample Input 3

1000000000 1000000000 1 1000000000 1000000000

Sample Output 3

1000000000000000000.0000000000000000

Your output will be considered correct when its absolute or relative error is at most $10^{-5}$.

问题描述

我们有一个$N$面的骰子，每面的数字分别为$1$到$N$，且出现的概率相等。
下面，骰子显示一个整数$X$，是指将骰子放置，使得上面的一面是数字$X$的一面。
最初，骰子显示整数$S$。

你可以在任意顺序、任意次数（包括零次）执行以下两个操作。

• 支付$A$日元（日本货币）将骰子显示的值“增加”$1$，即当它当前显示$X$时，重新放置它以显示$X+1$。当骰子显示$N$时，此操作不能执行。
• 支付$B$日元重新掷骰子，之后它将以相等的概率显示$1$到$N$之间的整数。

考虑从显示$S$的初始状态，使骰子显示$T$。
当使用最优策略以最小化期望成本时，输出所需的最小期望成本。

约束条件

• $1 \leq N \leq 10^9$
• $1 \leq S, T \leq N$
• $1 \leq A, B \leq 10^9$
• 输入中的所有值都是整数。

输入

输入从标准输入给出，格式如下：

$N$ $S$ $T$ $A$ $B$

输出

输出答案。 当绝对误差或相对误差小于等于$10^{-5}$时，你的输出将被认为是正确的。

样例输入1

5 2 4 10 4

样例输出1

15.0000000000000000

当使用最优策略以最小化期望成本时，所需的成本将是15日元。

样例输入2

10 6 6 1 2

样例输出2

0.0000000000000000

骰子在初始状态就已经显示$T$，这意味着不需要进行任何操作。

样例输入3

1000000000 1000000000 1 1000000000 1000000000

样例输出3

1000000000000000000.0000000000000000

当绝对误差或相对误差小于等于$10^{-5}$时，你的输出将被认为是正确的。