首页 > ACM题库 > HDU-杭电 > HDU 4159-Indomie-概率-[解题报告]HOJ
2015
05-23

HDU 4159-Indomie-概率-[解题报告]HOJ

Indomie

问题描述 :

During recession, Amjad needs to queue for SembakoPlus. Sembako, as we all know, stands for “Sembilan Bahan Pokok” which consists of 9 kinds of item: Rice, Sugar, Cooking-oil,Meat, Egg, Milk, Corn, Kerosene and Iodized Salt. SembakoPlus consists of Sembako and one more item: Indomie! Amjad’s favorite of all time!! (therefore, no wonder why he could stand for this long queue).
Each person in the queue is allowed to pick only one item. No need to ask, Amjad wants only Indomie. Unfortunately, they are running out of SembakoPlus stock and currently there are three kinds of item left: Rice, Sugar and Indomie. As he could see from afar, he is quite sure that Rice and Sugar will be enough for everybody.
Given the number of remaining Indomie and the number of people queuing in front of Amjad, your task is to count the probability that he will get his Indomie. Amjad can’t do programming right now as he is very nervous so he can’t think logically. He needs your help!

输入:

There will be multiple test cases for this problem. Each test case contains two integers N (1 ≤ N ≤ 50) and S (0 ≤ S ≤ 50), where N is the number of people queuing in front of Amjad and S is the remaining number of Indomie.

输出:

There will be multiple test cases for this problem. Each test case contains two integers N (1 ≤ N ≤ 50) and S (0 ≤ S ≤ 50), where N is the number of people queuing in front of Amjad and S is the remaining number of Indomie.

样例输入:

2 1
3 2
4 0
4 1
10 10
14 9
30 14

样例输出:

50.00000
76.92308
0.00000
33.33333
99.99831
98.65515
95.16071


Hint
Explanation for 1st sample test case: There are two peoples queuing in front of Amjad, so those two peoples could pick of the following combination {1st people, 2nd people}: 1. Rice, Rice 2. Rice, Sugar 3. Rice, Indomie 4. Sugar, Rice 5. Sugar, Sugar 6. Sugar, Indomie 7. Indomie, Rice 8. Indomie, Sugar Since there is only one Indomie left, there are only 4 out of 8 combinations that ensure Amjad to get his Indomie (1, 2, 4 and 5), hence the probability is 4/8 = 50%.

/*
分析:
    数学简单题,概率的。
没话说了,概率学的太烂了,这个题还是别人帮忙才做出来的。以后多
找点儿概率的题、学牢概率的知识,这题以后又机会了再试着做做。
    
注意当s>n时,直接输出100.00000,要不会WA的(参考别人代码后发现
的 – -I )。
所以以后更要注意对特殊情况的处理。

    思路:
用Ai表示前n个中,i个人取indomie的种类数。则
Ai=c(n,i)*pow(2,n-i)    (前者是n个人取i个indomie的种类数,后者
是其他人可以有rice和sugar两种选择)。
那么ans=∑Ai(0,1,2……s-1)/∑Ai(0,1,2……s)。

                                             2012-04-15(又凌晨了啊,
在学校很少有能刷到凌晨
的机会呢O(∩_∩)O~)
*/

#include"stdio.h"
#include"math.h"
double jie(int n)
{
	double y=1;
	int i;
	for(i=2;i<=n;i++)
		y*=i;
	return y;
}
double c(int n,int x)
{
	double z;
	z=jie(n)/jie(x)/jie(n-x);
	return z;
}
int main()
{
	double ans;
	int n;
	int s;
	double x,y;
	int i;
	while(scanf("%d%d",&n,&s)!=-1)
	{
		if(s>n)
		{
			printf("100.00000\n");
			continue;
		}
		x=y=0;
		for(i=0;i<s;i++)
			x+=c(n,i)*pow(2,n-i);
		for(i=0;i<=s;i++)
			y+=c(n,i)*pow(2,n-i);
		ans=x/y;
		printf("%0.5lf\n",ans*100);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7461938