http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1323. Contra(李超)
时间限制:3.0s   内存限制:512.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  偶然间,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游戏的一种可能性