| 题目名称 | 1778. [国家集训队2012]Contra |
|---|---|
| 输入输出 | nt2012_contra.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：19， 提交：43， 通过率：44.19% | ||||
 xyz117 |
100 | 0.532 s | 0.33 MiB | C++ |
 cstdio |
100 | 0.861 s | 0.31 MiB | C++ |
 wangxh |
100 | 1.127 s | 0.34 MiB | C++ |
 A_LEAF |
100 | 1.550 s | 1.05 MiB | C++ |
 呵呵酵母菌 |
100 | 1.964 s | 0.64 MiB | C++ |
 天亮说晚安· |
100 | 3.300 s | 0.61 MiB | C++ |
 LadyLex |
100 | 3.845 s | 0.50 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 5.096 s | 0.64 MiB | C++ |
 Hzoi_joker |
100 | 5.287 s | 9.68 MiB | C++ |
 Narcissus |
100 | 5.613 s | 0.44 MiB | C++ |
| 关于 Contra 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
没错，就是那种“概率型”的DP……
| ||||
BaDBoY
Contra(李超)
时间限制：3.0s 内存限制：512.0MB
【试题来源】
2012集训队互测-李超
【问题描述】
偶然间，chnlich发现了他小时候玩过的一个游戏“魂斗罗”，于是决定怀旧。但是这是一个奇怪的魂斗罗MOD。
有N个关卡，初始有Q条命。
每通过一个关卡，会得到u分和1条命，生命上限为Q。
其中u=min(最近一次连续通过的关数,R)。
若没有通过这个关卡，将会失去1条命，并进入下一个关卡。
当没有生命或没有未挑战过的关卡时，游戏结束，得到的分数为每关得到的分数的总和。
由于chnlich好久不玩这个游戏了，每条命通过每个关卡的概率均为p(0<=p<=1)，原先chnlich的最高分纪录是S。
现在chnlich想要知道，当p至少为多少时，chnlich期望获得的总分数能够超过原先的最高分。
有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是一个可能出现的分数。
对于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游戏的一种可能性
第一关：未通过 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游戏的一种可能性