Description
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 b
irthday? 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) 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
思路：
两个人生日相同的情况太多，用逆向思维，通过循环先算出任意两人生日不同的概率，若概率值小于等于0.5就可以了，结束循环；
计算任意两人生日不同的概率，用一个for循环，先算第一个人的是n*1.0 / n,第二个人的是(n-1) *1.0 / n,第三个人的是（n-2) *1.0 / n 等等；i从0开始，总人数为i+1(包括他自己），要邀请的人数是 i ;
代码：
#include<stdio.h> #include<string.h> int main() { int t,n,mm=1; scanf("%d",&t); while(t--) { double ans=1.0; scanf("%d",&n); int i; for(i=0;;i++) { ans*=(n-i)*1.0/n; if(ans<=0.5) break; } printf("Case %d: %d\n",mm++,i); } return 0; }
