No.1478 Simple Sugoroku
タグ : / 解いたユーザー数 131
作問者 :
nok0
/ テスター :
PCTprobability
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もしくは右上の雲マークをクリックしてアカウントを作成してください。