/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 N 以下の整数の目がそれぞれ等確率でランダムに出る N 面のサイコロがあります。
以下では、サイコロが整数 X の目を上にして置かれているとき、サイコロの「出目」が X であると言います。
はじめ、サイコロは出目が整数 S になるように置かれています。
このサイコロに対して、「下記の 2 つの操作のどちらかを行う」ということを好きな回数（ 0 回でもよい）だけ行うことができます。
- 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} 以下であれば正解として扱われます。
Score : 600 points
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}.