【数学】LightOJ1104 birthday parado（经典概率）

布满荆棘的人生 2022-09-25 05:19 6阅读 0赞

LightOJ1104 birthday parado

**Time Limit:**2000MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][] [Practice][] [LightOJ 1104][] [![12x12_uDebug.png][]uDebug][12x12_uDebug.png_uDebug]

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 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)** 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

365

669

Sample Output

Case 1: 22

Case 2: 30

竞赛时别人都写出来了，我竟没写出来，想复杂了， **拿到一个题要从战略上重视它，从战术上藐视它。**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int main() {
    	int T,p=0;
    	scanf("%d",&T);
    	while(T--) {
    		int n,i;
    		scanf("%d",&n);
    		double cnt=1.0;
    		for(i=0; i<n; i++) {
    			cnt=cnt*(1.0*n-1.0*i)/n*1.0;	//不知道cnt放后面乘为什么结果不对 
    			if(cnt<=0.5)
    				break;
    		}
    		printf("Case %d: %d\n",++p,i);
    	}
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/127946#status//I/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/26819
[LightOJ 1104]: http://acm.hust.edu.cn/vjudge/problem/26819/origin
[12x12_uDebug.png]: http://acm.hust.edu.cn/vjudge/images/12x12_uDebug.png
[12x12_uDebug.png_uDebug]: https://www.udebug.com/LOJ/1104