No.463 魔法使いのすごろく🎲

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下
タグ : / 解いたユーザー数 29
作問者 : tanzakutanzaku / テスター : 紙ぺーぱー紙ぺーぱー

4 ProblemId : 1450 / 出題時の順位表

問題文

トマトさんはすごろくをしています。
スタートはマス$1$でゴールはマス$n$です。
$1~m$の数値が書かれた$m$面さいころを振り出た目の数だけ進みます、その際ゴールを超えた分は折り返します。
スタートとゴールのマスを除くマス$i$には非負整数$c_i$が書かれており、そのマスに止まると$c_i$円失います。

トマトさんは一度だけ魔法を使い好きな目$(1~m)$を出すことができます。

トマトさんが失うお金を最小化するように最適に行動した時に失うお金の期待値を求めよ。
相対誤差または絶対誤差が$10^{-9}$以下の誤差まで許容されます。


・折り返しについて
$n=5$でマス4にいる時にさいころの目が2だった場合、マス4->マス5->マス4と移動する。

入力

$n$ $m$
$c_2$ $c_3$ ... $c_{n-1}$


1行目は、マスの数$n$とさいころの面の数$m$が与えられます。
2行目は、マスに止まった時に失う金額$c_i$が与えられます。

制約
$2 \le n\le 100$
$1 \le m < n$
$0 \le c_i\le 10^9$

入力は全て整数で与えられる。

出力

トマトさんが失うお金を最小化するように最適に行動した時に失うお金の期待値を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 1
1
出力
1

マス1 -> マス2 -> マス3と進み、1円失います

サンプル2
入力
4 2
1 1
出力
1

1度目の移動でマス2かマス3に移動します。
2度目の移動では、
・マス2にいる場合は魔法を使いさいころの目は2を出しゴールします。
・マス3にいる場合は魔法を使いさいころの目は1を出しゴールします。

サンプル3
入力
15 4
569741359 785505947 516548029 302116446 368843514 663681053 182054490 251269761 283218718 678332853 715581077 542832677 827187473
出力
2092731144.6443367000

提出ページヘ