UVA 10375 选择与除法 Choose and divide

选择与除法 Choose and divide

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

10 5 14 9
93 45 84 59
145 95 143 92
995 487 996 488
2000 1000 1999 999
9998 4999 9996 4998
1
2
3
4
5
6

样例输出 #1

0.12587
505606.46055
1.28223
0.48996
2.00000
3.99960
1
2
3
4
5
6

分析

对于:$$C(m,n)=\frac{m!}{(m-n)!n!}$$分母有mm项，显然分子有：$$m-n+n$$项，即上下项的相数相等。
当两个组合数相除时，这个性质也满足，所以可以边乘边除~

代码

#include

using namespace std;

int p,q,r,s;

int main()
{
	while(scanf("%d%d%d%d",&p,&q,&r,&s)!=EOF)
	{	
		double sum=1.00000;//保留5位
		
		int maxx=max(p-q,q);
		int maxxx=max(r-s,s);
		
		int n= max(maxx,maxxx);
		
		for(int i=1;i<=n;i++)
		{
			if(i<=maxx) //比较
			{
				sum=sum/i*(p+i-maxx);
			}
			
			if(i<=maxxx) 
			{
				sum=sum*i/(r+i-maxxx);
			}
		}
		
		printf("%.5f\n",sum);//保留5位
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35