[UVA][概率] 10217 - A Dinner with Schwarzenegger
A Dinner with Schwarzenegger !!!
Input: Standard Input
Output: Standard Output
Time Limit: 2 seconds
One of your friends informed you that a nearby theater in your city has given a new offer. It will show the super hit Schwarzenegger movie “Terminator 2”. While selling ticket they will keep record of the buyers' birthdays. If someone’s birthday matches the birthday of a person who has bought ticket before him, he (the one who bought ticket later) will be given the honor to have dinner with Schwarzenegger. To give the guy at the front of the queue some chance, his birthday will be compared with the ticket seller’s birthday. If you were given the chance, which position of the queue would you have wanted? (I know that many of you would have liked other names as a dinner partner. Don’t hesitate to replace Schwarzenegger with that name, as you may need all those inspirations to solve this problem.)
Fig: Arnold Schwarzenegger as Terminator
Input
The input file contains several lines of input. Each line contains an integer N (30<=N<100001), which indicates how many days make a year. Input is terminated by end of file.
Output
For each line of input, output one floating-point number and one integer in a single line, separated by a single space. The floating-point number is the best floating point position for you (with two digits after the decimal point) and the integer is the best integer position (in reality position must be an integer) for you in the queue.
Sample Input
365200
Sample Output
18.61 1913.65 14
Shahriar Manzoor
靠庫存頁面了
http://webcache.googleusercontent.com/search?q=cache:QFOWxxGvPIcJ:hi.baidu.com/drcrow/blog/item/3c83034c660dd6e382025c9e.html+&cd=4&hl=zh-TW&ct=clnk&gl=tw&client=firefox-a
以下說明為轉貼
问题大意：在一个队列中，第一个生日与前面某一个人相同的人最有可能是谁。假设一年有N日。
用P(i)表示第i个人符合条件的概率，则
由于这个人是第一个，所以先前不能有重复；
前面i-1个人的生日都不同时，他的生日与前面i-1个人中的某一个相同的概率是(i-1)/n.
所以
P(i)=(1-sigma(P(j),1<=j<i))*(i-1)/n.
P(0)=1.
UVa的原题中要求输出是实数（比如n=365时答案是18.61,而不是19），所以问题还没完。
首先，我们需要导出一个P(i)与P(i-1)的关系式，或者说，P(i+1)与P(i)的关系。
令S(i)=sigma(P(j),1<=j<=i)，则
P(i)=(1-S(i-1))*(i-1)/n, =>
S(i-1)=1-P(i)*n/(i-1) =>
S(i)=S(i-1)+P(i)=1+(i-1-n)/(i-1)*P(i) =>
P(i+1)=(1-S(i))*i/n=[(n-i+1)*i]/[(i-1)*n]*P(i).
经过程序的测试，P是双调的，就是先递增，再递减。（这个也可以证明）
令U表示式子中，P(i)的系数。当P递增时，系数U应该是一直大于1的，这一点显然；＆ vice versa.
在U刚好小于1时，P达到最大值。也就是[(n-i+1)*i]/[(i-1)*n]<1.
解这个关于i的不等式即可.
最後採用牛頓法求解。公式解看不是很懂。
#include <stdio.h>
#include <math.h>
#include <string.h>
double f(double x, double n) {
return x * (n - x + 1) / ((x-1) * n) - 1;
}
double fd(double x, double n) {
return ((n - 2*x + 1)*(x - 1) - x * (n - x + 1))/ (n * (x-1) * (x-1));
}
// Let P(i) be i-th people happened same.
// P(0) = 1
// P(i) = (1 - sigma(P(j), 1<=j<i)) * (i-1)/n
// Let S(i) = sigma(P(j), 1<=j<=i)
// P(i) = (1 - S(i-1)) * (i-1)/n
// => S(i-1) = 1 - P(i) * n / (i-1)
// S(i) = S(i-1) + P(i) = 1 + (i-1-n)/(i-1) * P(i)
// => P(i+1) = (1 - S(i)) * i/n = [(n-i+1)*i]/[(i-1)*n]*P(i)
// => P(i+1)/P(i) < 1, increase then decrease
// => [(n-i+1)*i]/[(i-1)*n] < 1
// => f(x) = [(n - x + 1)*x / (x - 1)] / [(x - 1) * n] - 1
// => f'(x) = ...
int main() {
int n;
/*freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);*/
while(scanf("%d", &n) == 1) {
double x = n;
int cnt = 0;
while(cnt++ < 30) {
x = x - f(x, n)/fd(x, n);
}
printf("%.2lf %d\n", x - 1, (int)ceil(x - 1 + 1e-8));
}
return 0;
}