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