問題一覧 > 通常問題

No.1478 Simple Sugoroku

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-4}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 131
作問者 : nok0 / テスター : fairy_lettuce otera ygussany PCTprobability
お気に入りにしたユーザー ProblemId : 5790 / 自分の提出
問題文最終更新日: 2021-03-21 12:17:15
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
yukicoder contest 291 (順位表) の他の問題:

Problem Statement

nok0 is playing sugoroku.

This sugoroku board has $N$ squares arranged in a line, numbered $1,2,\dots,N$ from left to right.

Of these squares, the $M$ squares $B_1,B_2,\dots,B_M$ are warp squares.

nok0 starts on square $1$, and until he moves to square $N$, he repeatedly chooses and performs one of the following $2$ operations.

  • Operation $1$ : Let square $i$ be the square nok0 is currently on. Move to square $i+1$.
  • Operation $2$ : This operation can be chosen only when the square nok0 is currently on is a warp square. Choose one warp square (including the square nok0 is on) uniformly at random and move to that warp square.

Find the expected number of operations when nok0 acts so as to minimize the expected number of operations.

Constraints

  • All inputs are integers.
  • $1\le N\le 10^9$
  • $1\le M \le \mathrm{min}(N,10^5)$
  • $ 1 \le B_1 < B_2 < \dots < B_M \le N$

Input

$N\ M$
$B_1\ B_2\ \dots\ B_M$

Output

Output the expected number of operations when nok0 acts so as to minimize the expected number of operations. Your answer is considered correct if its absolute or relative error from the correct value is at most $10^{-4}$.

Sample

Sample 1
Input
2 1
2
Output
1.0

Performing operation $1$ for $1$ time reaches the goal.

Sample 2
Input
100 2
1 100
Output
2.00

It is optimal to repeat operation $2$ until reaching the goal. The expected number of operations is $\displaystyle\sum_{i=1}^{\infty} \left(\frac{1}{2}\right)^ii = 2.0$.

Sample 3
Input
10000 9
100 200 300 400 1900 1901 2900 2901 2904
Output
7200.3333333333

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。