#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游戏的一种可能性