LightOJ 1104

题意:

　　给你一年有n天，求至少有m人使得至少有两个人在同一天生日的概率不少于0.5.

分析:

　　任意两个人不在同一天生日的概率为C(n,m)*m!/n^m,它的对立事件A为至少有两个人在同一天生日,

则P(A) = 1 - C(n,m)*m!/n^m = 1 - P(n,m)/n^m(后一个P表示排列); 根据题意有P(A) >= 0.5 即 P(n, m)/n^m <= 0.5.

该式的展开式为 p = n/n*(n-1)/n*(n-2)/n*...*(n-m+1)/n,因此只要判断该式的累乘结果小于等于0.5时,输出此时的m即可.

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <vector>

using namespace std;

#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 10000010
#define MAXM 1000010


int main()
{
    int kase = 0;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        double p = 1.0;
        int cnt = 0;
        while(p > 0.5)
        {
            p *= 1.0*(n-cnt)/n;
            cnt++;
        }
        printf("Case %d: %d
", ++kase, cnt-1);
    }
    return 0;
}