#abc189f. [abc189_f]Sugoroku2
[abc189_f]Sugoroku2
题目描述
高桥正在玩游戏。
游戏板有 个方格,编号从 到 。高桥从方格 出发,前往方格 。
在这个游戏中,我们使用一个可以显示从 到 的数字的轮盘,每个数字出现的概率相同。每次操作中,高桥转动轮盘,并按照轮盘上所示的数字前进相应的步数。当他到达或超过方格 时,他获胜。
其中一些方格在高桥停在它们上面时将他送回方格 。共有 个这样的方格:方格 。
求高桥赢得比赛前转动轮盘的次数的期望值。如果无法赢得比赛,请输出 -1
。
约束条件
- 输入中的所有值都是整数。
输入
从标准输入读入数据,输入格式如下:
输出
打印高桥赢得比赛前转动轮盘的次数的期望值。当你的输出与我们的答案的绝对误差或相对误差最大为 时,将其视为正确。如果无法赢得比赛,请输出 -1
。
示例输入 1
2 2 0
示例输出 1
1.5000
如果在第一次转动轮盘时出现 ,他将需要两次转动才能获胜;如果在第一次转动轮盘时出现 ,他将需要一次转动才能获胜。因此,转动轮盘的次数的期望值是 。
示例输入 2
2 2 1
1
示例输出 2
2.0000
如果在第一次转动轮盘时出现 ,他将前进到方格 ,但它会将他送回方格 。因此,他将继续转动轮盘,直到获得 并获胜。他在第 次转动中第一次得到 的概率是 ,因此转动轮盘的次数的期望值是 $\\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