LightOj_1104 Birthday Paradox

 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 INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 100010
22 #define MAXM 380
23 double f[MAXN];
24 int n;
25 void init()
26 {
27     double x, y;
28     double m;
29     f[0] = 0;
30     f[1] = 1;
31     for(int i = 2; i < MAXN; i ++)
32     {
33         m = i;
34         y = i - 1.0;
35         x = 1.0;
36         for(int j = 1; j < MAXM; j ++)
37         {
38             x = x * y;
39             x /= m;
40             y --;
41             if(x <= 0.5)
42             {
43                 f[i] = j;
44                 break;
45             }
46         }
47     }
48 }
49 
50 int main()
51 {
52     int T;
53     int kcase = 0;
54     init();
55     scanf("%d", &T);
56     while(T --)
57     {
58         scanf("%d", &n);
59         printf("Case %d: %.0lf\n", ++kcase, f[n]);
60     }
61     return 0;
62 }