简介：
每天晚上你都会玩纸牌游戏，如果第一次就赢了就高高兴兴的去睡觉，如果输了就继续玩，假设每盘游戏你获胜的概率都是p。你是一个固执的完美主义者，一定会玩到当晚获胜局数的比例严格大于p时才停止，然后高高兴兴的去睡觉，当然晚上的时间有限，所以你最多只能玩n局，如果获胜比例一直无法超过p，你就会垂头丧气的去睡觉，再也不玩纸牌了，你的任务是计算在平均状态下，你会玩多少晚上。
分析：
不难发现，每天晚上的情况都是独立的，所以我们先来看一下单独一天的情况，
计算出只玩一晚上，“垂头丧气的去睡觉”的概率Q
设f[i][j]表示前i局，每局结束的时候获胜的比例都不超过p，且前i局一共获胜j场
则根据全概率公式得到：
当j/i<=p时， f[i][j]=f[i-1][j]*(1-p)+f[i-1][j-1]*p
其余情况f[i][j]=0
边界情况为f[0][0]=1 , f[0][1]=0
则f[n][0]+f[n][1]+f[n][2]+…就是所求的Q
下面我们用数学期望的定义来计算游戏总天数X的数学期望：
X=1的概率是Q
X=2的概率是Q(1-Q)：第一天高高兴兴，第二天垂头丧气
X=3的概率是Q(1-Q)^2：前两天高高兴兴，第三天垂头丧气
… …
X=k的概率是Q(1-Q)^(k-1)：前k-1天高高兴兴，第k天垂头丧气
因此X的数学期望
EX = 1*Q + 2*Q(1-Q) + 3*(1-Q)^2 + 4*(1-Q)^3…
注意这是一个无穷级数，所以ta的计算需要一点数学技巧：
注意到ta的形式是等差数列和等比数列乘积的前缀和，所以我们可以用错位相减
实际上我们还可以通过一个更简单额方式得到EX：
设数学期望为e天，
把情况分为两类：第一天晚上垂头丧气，概率为Q，数学期望为1
第一天晚上高高兴兴，概率为1-Q，数学期望为e+1
根据全期望公式：e=Q*1+(1-Q)*(e+1)
解得e=1/Q
tip
数组千万不要开太大，这样会影响时间
千万不要无脑循环
一旦 j/i>p 就停止循环
在判断j/i>p的时候我用到了dcmp，避免精度问题，
当然还有一种更优美的循环方式
memset(f,0,sizeof(f));
f[0][0]=1; f[0][1]=0;
for (int i=1;i<=n;i++) for (int j=0;j*b<=i*a;j++) { f[i][j]=f[i-1][j]*(1-p); f (j) f[i][j]+=f[i-1][j-1]*p; } 这样既可以避免精度问题，又可以不用额外写dcmp
//这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-8;
double f[105][105];
int dcmp(double x)
{
if (fabs(x)<eps) return 0;
else if (x>0) return 1;
else return -1;
}
int main()
{
int T;
scanf("%d",&T);
for (int cas=1;cas<=T;cas++)
{
int n,a,b;
scanf("%d/%d%d",&a,&b,&n); //注意读入格式
double p=(double)a/b;
memset(f,0,sizeof(f));
f[0][0]=1; f[0][1]=0;
for (int i=1;i<=n;i++)
for (int j=0;dcmp((double)j/i-p)<=0;j++)
{
f[i][j]=f[i-1][j]*(1-p);
if (j) f[i][j]+=f[i-1][j-1]*p;
}
double Q=0;
for (int i=0;dcmp((double)i/n-p)<=0;i++)
Q+=f[n][i];
printf("Case #%d: %d\n",cas,(int)(1/Q));
}
return 0;
}