No.463 The Wizard's Sugoroku 🎲
Problem Statement
Tomato-san is playing sugoroku.
The start is square $1$ and the goal is square $n$.
On each move, Tomato-san rolls an $m$-sided die with the numbers $1~m$ written on it and advances by the number rolled; any amount exceeding the goal is bounced back.
Each square $i$, except for the start and goal squares, has a non-negative integer $c_i$ written on it, and stopping on that square costs $c_i$ yen.
Once only, Tomato-san can use magic to roll any number of choice $(1~m)$.
Find the expected value of the money lost when Tomato-san acts optimally to minimize the money lost.
An error of up to $10^{-9}$ in relative or absolute error is allowed.
・About bouncing back
If $n=5$ and the die shows 2 while on square 4, the movement is square 4 -> square 5 -> square 4.
Input
$n$ $m$
$c_2$ $c_3$ ... $c_{n-1}$
The first line gives the number of squares $n$ and the number of faces of the die $m$.
The second line gives the amounts $c_i$ lost when stopping on the squares.
Constraints
$2 \le n\le 100$
$1 \le m < n$
$0 \le c_i\le 10^9$
All inputs are given as integers.
Output
Output the expected value of the money lost when Tomato-san acts optimally to minimize the money lost.
Print a newline at the end.
Sample
Sample 1
Input
3 1 1
Output
1
The movement is square 1 -> square 2 -> square 3, and 1 yen is lost.
Sample 2
Input
4 2 1 1
Output
1
The first move goes to square 2 or square 3.
On the second move:
・If on square 2, use magic to roll a 2 and reach the goal.
・If on square 3, use magic to roll a 1 and reach the goal.
Sample 3
Input
15 4 569741359 785505947 516548029 302116446 368843514 663681053 182054490 251269761 283218718 678332853 715581077 542832677 827187473
Output
2092731144.6443367000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tanzaku
紙ぺーぱー