| 题目名称 | 1489. [UVa 11427] 玩纸牌 |
|---|---|
| 输入输出 | expected.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-01-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：81， 提交：179， 通过率：45.25% | ||||
 AntiLeaf |
100 | 0.077 s | 0.29 MiB | C++ |
 远航之曲 |
100 | 0.095 s | 0.29 MiB | C++ |
 雾茗 |
100 | 0.096 s | 0.29 MiB | C++ |
 Lenar |
100 | 0.101 s | 0.14 MiB | C++ |
|
AntiLeaf |
100 | 0.110 s | 0.29 MiB | C++ |
 niconicoqaq |
100 | 0.112 s | 0.39 MiB | C++ |
 sxysxy |
100 | 0.130 s | 0.37 MiB | C++ |
 MayBe |
100 | 0.133 s | 0.39 MiB | C++ |
 真呆菌 |
100 | 0.136 s | 7.94 MiB | C++ |
 QwQ |
100 | 0.139 s | 0.25 MiB | C++ |
| 关于 玩纸牌 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
快把我调哭了
lemon上跑不过，cogs上跑不过，下下来数据fc无差异 完全不知道怎么debug 最后把*p换了换就过了？  CSU_Turkey
2017-10-20 20:51
10楼
| ||||
|
我太垃圾了
CSU_Turkey
2017-10-20 19:40
9楼
| ||||
|
按照白书的j*b<=a*i就T掉了,把这个乘法预处理下就过掉了23333QAQ
 404
2017-03-30 19:11
8楼
| ||||
|
说好的答案允许有±1的误差，为什么给我WA
| ||||
|
强行滚动数组......
| ||||
|
数组开太大，memset被卡TLE了。。。注意N是数据组数，n的范围是300而不是300
 liu_runda
2016-12-16 18:58
5楼
| ||||
|
回复 @Chenyao :
就是说，当玩的次数趋近于无穷的时候，你一直没达到目标的概率趋近于零 | ||||
|
回复 @cstdio :
咦，好像是呀，分母无很大的时候分子也可能和”标准“差很大，是不是可以这样理解  Chenyao2333
2014-01-17 22:52
3楼
| ||||
|
回复 @Chenyao :
无穷次的确可以啊…… | ||||
|
"宣布自己保持了获胜比例大于p*100%。我打败了数学规律"数学神犇，我想问个问题，如果一个人可以一天玩无数次，直到大于p*100%才停止，是不是真的可以说获胜比例大于p*100%，似乎是不是没有什么不妥啊。。。
Chenyao2333
2014-01-17 21:58
1楼
| ||||
MistyEye
cstdio【题目描述】
本题目有一定的数学背景。
题中要求计算一个随机变量的期望值。如果你之前没有听说过这些数学名词，下面给出了一些简单的定义。一个随机变量是一个可以取若干个值的变量，对于每个可能值，它都有一定概率取这个值。取到每个可能值的概率都是正的，并且它们的和是1.随机变量的数学期望是它所有可能值与其对应概率之积的乘积总和（对它有一些更为复杂，形式化的定义，但你现在不需要用到这些）。例如，一个标准的6面骰子投出后上面的值是一个随机变量，有6个可能值（1到6），取到每个可能值的概率都是1/6.那么它的数学期望就是1/6+2/6+...+6/6=3.5.
下面是题目内容。
我喜欢玩纸牌接龙。每次我都有p的概率赢，1-p的概率输。游戏程序会统计我获胜盘数的百分比。如果我一直玩下去，这个百分比就会在p*100%左右浮动。但我仍不满足。
这是我的计划。每天，我都会玩纸牌接龙。如果我赢了，我就高高兴兴地去睡觉。如果我输了，我就一直玩下去直到我这天获胜盘数的百分比严格大于p。这时，我就会宣布胜利，然后高高兴兴地去睡觉。你可以看到，每天我都可以宣布自己保持了获胜比例大于p*100%。我打败了数学规律！
如果你感觉这里好像有什么奇怪的东西，那你就对了。我不可能永远这么做，因为我每天玩的游戏盘数有限。我每天至多玩n盘游戏。那么，这个机智的计划在因为这一限制失败前，执行天数的数学期望是多少？值得注意的是，答案至少为1，因为我至少要玩一天才能发现计划失败了。
【输入格式】
输入包含多组数据。
输入文件的第一行是数据组数N。
接下来是N组数据。每组数据有一行，包含p（写成分数）和n。
【输出格式】
对于每组数据，输出一行"Case #x: y"，其中x是数据组数（从1开始），y是期望天数，向下取整。
【样例输入】
4 1/2 1 1/2 2 0/1 10 1/2 3
【样例输出】
Case #1: 2 Case #2: 2 Case #3: 1 Case #4: 2
【提示】
1<=N<=3000,0<=p<1
p的分母不超过1000。
1<=n<=100。
答案允许有±1的误差。
【来源】
UVa 11427 Expecte the Expected
刘汝佳，《算法竞赛入门经典训练指南》表2.8