网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
玩纸牌
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | expected.in | 输出文件 | expected.out |
【题目描述】
本题目有一定的数学背景。
题中要求计算一个随机变量的期望值。如果你之前没有听说过这些数学名词,下面给出了一些简单的定义。一个随机变量是一个可以取若干个值的变量,对于每个可能值,它都有一定概率取这个值。取到每个可能值的概率都是正的,并且它们的和是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的误差。
【来源】
刘汝佳,《算法竞赛入门经典训练指南》表2.8