由于 UCup 也缺头,且下下一题的造题 AI 效果不尽如意,鱼王青鱼重新训练了一个 New AI。
题目描述
鱼王青鱼的 New AI 不愿意进行 996 的工作,于是要求青鱼先和它玩一个游戏。
玩家玩一个打怪兽的游戏,玩家有 $n$ 点血量,怪兽有 $m$ 点血量。
在任意时刻,玩家可以选择以下两种操作之一:
- (攻击):玩家释放一次攻击技能,此时玩家需要消耗 $1$ 单位的时间进行冷却。在冷却结束后,有 $p$ 的概率玩家攻击成功,此时怪兽的血量减少 $1$ 点。同时,有 $1-p$ 的概率玩家失败,此时玩家的血量减少一点。
- (重开):玩家放弃这轮比赛,决定重新开始。该操作不需要花费任何时间,同时玩家的血量变回 $n$,怪兽的血量变回 $m$。
当玩家的血量变为 $0$ 时,玩家便会死亡,此时玩家只能选择重开。而当怪兽的血量变为 $0$ 时,玩家便取得了胜利。
青鱼想要知道,如果玩家采取最优的策略,那么期望情况下需要消耗多少时间玩家才能取得胜利?
由于青鱼游玩的时间不能超过 $10^9$ 单位时间,因此如果在经历了 $10^9$ 单位时间后还无法取得胜利,则输出 $10^9$ 即可。
输入格式
输入只有一行,包含三个整数 $n, m, c$,其中 $p = \displaystyle \frac{c}{100}$。
输出格式
输出一行一个实数,表示答案与 $10^9$ 的最小值。
你的答案会被认为是正确的,当且仅当其与标准答案的相对误差或绝对误差不超过 $10^{-6}$。
样例数据
样例 1 输入
2 1 10
样例 1 输出
10.0
样例 1 解释
由于怪兽只有 $1$ 点血量,因此问题的答案即为玩家期望攻击多少轮可以击杀怪兽,答案即为 $1/p = 10$。需要注意的是由于重开不需要任何时间,因此玩家的死亡不会影响答案。
样例 2 输入
2 2 1
样例 2 输出
5125.12562814070456340687
样例 3 输入
50 60 99
样例 3 输出
60.60606060606060606355
样例 4 输入
114 514 19
样例 4 输出
1000000000.00000000000000000000
数据范围
本题采用捆绑测试,你需要通过一个子任务的所有测试点才能得到子任务的分数。
对于所有数据,$1 \leq n,m \leq 1\,000$,$0 < c < 100$。详细数据范围如下表。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
$1$ | $n=1$ | $10$ |
$2$ | $n\leq 2$ | $10$ |
$3$ | $n\leq 3$ | $10$ |
$4$ | $m=1$ | $10$ |
$5$ | $m\leq 2$ | $10$ |
$6$ | $m\leq 3$ | $10$ |
$7$ | $n,m\leq 10$ | $10$ |
$8$ | $c=1$ | $15$ |
$9$ | 没有额外的限制 | $15$ |