Roll or Increment

题目描述

我们有一个 $N$ 面的骰子（dice 的单数），它以相等的概率显示从 $1$ 到 $N$ 的整数。
下面，当骰子被放置使得顶部面为整数 $X$ 的面时，我们称骰子显示整数 $X$。
最初，骰子显示整数 $S$。 你可以对这个骰子任意次（可能为零次）以任意顺序执行以下两种操作。

支付 $A$ 日元将骰子显示的值“增加” $1$，也就是说，当它当前显示 $X$ 时，将其重新放置为显示 $X+1$。当骰子显示 $N$ 时不能执行此操作。 支付 $B$ 日元重新投掷骰子，之后它将以相等的概率显示 $1$ 到 $N$ 之间的一个整数。

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

输入格式

输入按以下格式从标准输入给出： $N$ $S$ $T$ $A$ $B$

输出格式

输出答案。 当你的输出的绝对误差或相对误差至多为 $10^{-5}$ 时，将被视为正确。

5 2 4 10 4

15.0000000000000000

10 6 6 1 2

0.0000000000000000

1000000000 1000000000 1 1000000000 1000000000

1000000000000000000.0000000000000000

提示

$1 \leq N \leq 10^9$ $1 \leq S, T \leq N$ $1 \leq A, B \leq 10^9$ 输入中的所有数值均为整数。当使用最优策略以最小化期望成本时，值将为 $15$ 日元。
初始状态下骰子已经显示 $T$，这意味着不需要任何操作。
当你的输出的绝对误差或相对误差至多为 $10^{-5}$ 时，将被视为正确。

标签: AtCoder|abc224G

来源

AtCoder|abc224G