UVA 10217 A Dinner with Schwarzenegger!!!---数学

题目链接：

https://cn.vjudge.net/problem/UVA-10217

题目大意：

有若干人排队买电影票，如果某个人的生日与排在他前面的某个人的生日相同，那么他讲中奖。中奖的机会只有一个，给所有中奖者中排在最前面的那一位。排在第一位的人如果与买票者的生日相同，那么他将中奖。如果一年有N天，求排在什么位置的中奖概率最大，和理论上的最佳实数位置。

解题思路：

f[1] = 1/n;

f[2] = (n-1)/n * 1/n;

...

f[i] = (n-1)/n * (n-1)/n * (n-2)/n * ... * (n-i+2)/n * (i-1)/n;

f[i+1] = (n-1)/n * (n-1)/n * (n-2)/n * ... * (n-i+1)/n * i/n;

所以f[i]/f[i+1] = (i-1)*n/[(n-i+1)*i]令其<=1解得：

(1-sqrt(4*n+1)) / 2 <= i <= (1+sqrt(4*n+1)) / 2;

故最佳整数位置为ceil((1+sqrt(4*n+1)) / 2)，最佳实数位置根据样例来看是(-1+sqrt(4*n+1)) / 2。

 #include<cstdio>

 #include<math.h>

 int n;

 int main(){

     while(~scanf("%d",&n)){

         double ans = (-1.0+sqrt(1.0 + 4.0*n)) / 2.0;

         int res = ans+1.0;

         printf("%.2lf %d\n",ans,res);

     }

     return ;

 }

巴特西

UVA 10217 A Dinner with Schwarzenegger!!!---数学

最新文章

热门文章