/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N の番号がついた N+1 個のマスがあります。 高橋君はマス 0 からスタートし、マス N を目指します。
この双六では、1 から M までの M 種類の目が等確率で出るルーレットを使います。 各手番で、高橋君はルーレットを回して出た目の数だけ進みます。この結果マス N に到達するか、マス N を越えて進むことになる場合、ゴールとなります。
また、いくつかのマスは「振り出しに戻る」であり、それらのマスに止まると、マス 0 まで戻されます。 そのようなマスは K 個あり、マス A_1,\ldots,A_K です。
高橋君がゴールするまでにルーレットを回す回数の期待値を答えてください。
ゴールすることが不可能な場合は、かわりに -1 を出力してください。
制約
- 入力はすべて整数
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq K \leq 10
- 0 < A_1 < \ldots < A_K < N
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 \ldots A_K
出力
高橋君がゴールするまでにルーレットを回す回数の期待値を出力せよ。
なお、想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。
ただし、ゴールすることが不可能な場合は、かわりに -1 と出力せよ。
入力例 1
2 2 0
出力例 1
1.5000
1 回目のルーレットで 1 を出した場合は 2 回、2 を出した場合は 1 回でゴールできるので、ルーレットを回す回数の期待値は 1.5 です。
入力例 2
2 2 1 1
出力例 2
2.0000
ルーレットで 1 を出すとマス 1 に移動しますが、このマスは「振り出しに戻る」なのでマス 0 に戻されます。
従って、2 が出るまでルーレットを回し続け、2 が初めて出た時点でゴールすることになります。
i 回目に初めて 2 が出る確率は \frac{1}{2^i} ですから、ルーレットを回す回数の期待値は \sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2 となります。
入力例 3
100 6 10 11 12 13 14 15 16 17 18 19 20
出力例 3
-1
入力例 4
100000 2 2 2997 92458
出力例 4
201932.2222
Score : 600 points
Problem Statement
Takahashi is playing sugoroku.
The board has N+1 squares numbered 0 to N. Takahashi starts at Square 0 and head to Square N.
In this sugoroku, we use a wheel showing numbers from 1 through M with equal probability. In each turn, Takahashi spins the wheel and advances by the number shown by the wheel. When it makes him reach Square N or go past it, he wins.
Some of the squares send him to Square 0 when he stops on them. There are K such squares: Square A_1, \ldots, A_K.
Find the expected value of the number of times Takahashi spins the wheel before he wins.
If it is impossible to win, print -1 instead.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq K \leq 10
- 0 < A_1 < \ldots < A_K < N
Input
Input is given from Standard Input in the following format:
N M K A_1 \ldots A_K
Output
Print the expected value of the number of times Takahashi spins the wheel before he wins.
Your output is considered as correct when its absolute or relative error from our answer is at most 10^{-3}.
If it is impossible to win, print -1 instead.
Sample Input 1
2 2 0
Sample Output 1
1.5000
If the wheel shows 1 in the first spin, he will need two spins to win; if the wheel shows 2 in the first spin, he will need one spin to win. Thus, the expected number of spins is 1.5.
Sample Input 2
2 2 1 1
Sample Output 2
2.0000
If the wheel shows 1, he advances to Square 1, but it sends him back to Square 0.
Thus, he keeps spinning the wheel until he gets 2 and wins.
The probability that he gets 2 for the first time in the i-th spin is \frac{1}{2^i}, so the expected number of spins is \sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2.
Sample Input 3
100 6 10 11 12 13 14 15 16 17 18 19 20
Sample Output 3
-1
Sample Input 4
100000 2 2 2997 92458
Sample Output 4
201932.2222