Birthday Paradox LightOJ - 1104

86 阅读 0 评论 57 点赞

我是靠谱客的博主狂野水壶，最近开发中收集的这篇文章主要介绍Birthday Paradox LightOJ - 1104，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sometimes some mathematical results are hard to believe. One of the common problems is the birthday paradox. Suppose you are in a party where there are 23 people including you. What is the probability that at least two people in the party have same birthday? Surprisingly the result is more than 0.5. Now here you have to do the opposite. You have given the number of days in a year. Remember that you can be in a different planet, for example, in Mars, a year is 669 days long. You have to find the minimum number of people you have to invite in a party such that the probability of at least two people in the party have same birthday is at least 0.5.

Input

Input starts with an integer T (≤ 20000), denoting the number of test cases.
Each case contains an integer n (1 ≤ n ≤ 105 10 5 ) in a single line, denoting the number of days in a year in the planet.

Output

For each case, print the case number and the desired result.

Sample Input

2
365
669

Sample Output

Case 1: 22
Case 2: 30

Solution

已知某星球一年有多少天，要求的是至少两个人的生日在一年之中的同一天，最少需要找多少人。

逆向思维

地球上的n个人的生日不在同一天的概率：P=365*365/364*365*…*(1+365-n)/365,有了这个反向找最小的n即可

#include<bits/stdc++.h>
#define ll long long
#define L(u) u<<1
#define R(u) u<<1|1
using namespace std;
const int MX = 101;
int T, n, ans;
int val[MX];
double f[MX*MX];
double p[MX],P;
int main() {
//freopen("../in", "r", stdin);
scanf("%d",&T);
for (int I=1;I<=T;++I) {
printf("Case %d: ",I);
scanf("%d",&n);
P=1;
ans=1;
while (P>0.5) {
ans++;
P*=1.0*(n+1-ans)/n;
}
printf("%dn",ans-1);
}
return 0;
}