Uva_11427 Expect the Expected

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 110
19 #define MOD 1000000007
20 #define eps 1e-6
21 double p;
22 int a, b;
23 int n;
24 double dp[MAXN][MAXN];
25 void init()
26 {
27     memset(dp, 0, sizeof(dp));
28     dp[0][0] = 1;
29     dp[0][1] = 0;
30 
31     for(int i = 1; i <= n; i ++)
32     {
33         dp[i][0] = dp[i-1][0] * (1.0 - p);
34         for(int j = 1; j * b <= a * i; j ++)
35             dp[i][j] = dp[i-1][j] * (1.0 - p) + dp[i-1][j-1] * p;
36     }
37 }
38 
39 int main()
40 {
41     int T;
42     int kcase = 0;
43     scanf("%d", &T);
44     while(T --)
45     {
46         scanf("%d/%d %d", &a, &b, &n);
47         p = (double)a / (double)b;
48         init();
49         double ans = 0.0;
50         for(int i = 0; i * b <= n * a; i ++) 
51             ans += dp[n][i];
52         ans = 1 / ans;
53         printf("Case #%d: %d\n", ++ kcase, (int)ans);
54     }
55     return 0;
56 }