Roll or Increment

AtCoder

IDabc224_g

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

5 2 4 10 4

Output #1

15.0000000000000000

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

Input #2

10 6 6 1 2

Output #2

0.0000000000000000

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

Input #3

1000000000 1000000000 1 1000000000 1000000000

Output #3

1000000000000000000.0000000000000000

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

API Response (JSON)

{
  "problem": {
    "name": "Roll or Increment",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc224_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a $N$\\-face die (singular of dice) that shows integers from $1$ through $N$ with equal probability.  \nBelow, the die is said to be showing an integer $X$ when it is placed so that the top face...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments