問題一覧 > 通常問題

No.463 The Wizard's Sugoroku 🎲

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 48
作問者 : tanzaku / テスター : 紙ぺーぱー
お気に入りにしたユーザー ProblemId : 1450 / 自分の提出
問題文最終更新日: 2026-06-25 18:26:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。