#1672. 2676. Contra
2676. Contra
#2676. Contra
题目描述
偶然间,chnlich发现了他小时候玩过的一个游戏"魂斗罗",于是决定怀旧。但是这是一个奇怪的魂斗罗MOD。
有N个关卡,初始有Q条命。
每通过一个关卡,会得到u分和1条命,生命上限为Q。
其中u=min(最近一次连续通过的关数,R)。
若没有通过这个关卡,将会失去1条命,并进入下一个关卡。
当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。
由于chnlich好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先chnlich的最高分纪录是S。
现在chnlich想要知道,当p至少为多少时,chnlich期望获得的总分数能够超过原先的最高分。
输入格式
输入共一行,分别表示整数N,整数R,整数Q,原先的最高分整数S。
输出格式
输出共一行,若不存在这样的p,输出"Impossible."(不包含引号),否则输出p(保留6位小数)。
样例
样例输入
样例输入一
4 2 1 5
样例输出一
0.880606
样例输入二
12 3 2 12
样例输出二
0.687201
样例输出
数据范围与提示
数据规模和约定
对于20%的数据,N<=15
对于50%的数据,N<=10000
对于100%的数据,N<=10^8,1<=R<=20,1<=Q<=5,保证S是一个可能出现的分数。
补充说明
例如,当N=12,R=3,Q=2时
第一关:未通过 u=0 获得分数0 总分为0 剩余生命1
第二关:通过 获得分数1 总分为1 剩余生命2
第三关:通过 获得分数2 总分为3 剩余生命2
第四关:通过 获得分数3 总分为6 剩余生命2
第五关:通过 获得分数3 总分为9 剩余生命2
第六关:未通过 获得分数0 总分为9 剩余生命1
第七关:通过 获得分数1 总分为10 剩余生命2
第八关:未通过 获得分数0 总分为10 剩余生命1
第九关:未通过 获得分数0 总分为10 剩余生命0
游戏结束 总分为10
这是chnlich游戏的一种可能性