BZPRO

#2676. Contra

内存限制：512 MiB 时间限制：30 Sec
提交 提交记录 讨论

题目描述

　　偶然间，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游戏的一种可能性

BZPRO Powered by Remmina.
Github Repository