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