首页 > 代码库 > Codeforces Round #272 (Div. 2) B. Dreamoon and WiFi (超几何分布)

Codeforces Round #272 (Div. 2) B. Dreamoon and WiFi (超几何分布)

题目链接:Codeforces Round #273 (Div. 2) B. Dreamoon and WiFi

题意:“+”表示前进1个单位,“-”表示后退1个单位,问以0为起点经过S1,S2两个命令后达到的位置相同的概率。

思路:统计“+”和“-”的数量。如果S2中的“+”或者“-”比S1中的多,概率是0。其他条件下,形成的是超几何分布。


AC代码:


#include <stdio.h>
#include <string.h>
int fac(int n,int m)
{
	int i,s=1;
	for(i=m;i>m-n;i--)
		s*=i;
	return s;
}
int C(int n,int m)
{
	int a=fac(n,m);
	int b=fac(n,n);
	return a/b;
}
double ipow(double n,int p)
{
	int i;
	double s=1.0;
	for(i=0;i<p;i++)
		s*=n;
	return s;
}
int main()
{
	char s1[20],s2[20];
	int len,i;
	while(scanf("%s",s1)!=EOF)
	{
		len=strlen(s1);
		int addsum,subsum;
		addsum=subsum=0;
		for(i=0;i<len;i++)
		{
			if(s1[i]=='+') addsum++;
			else subsum++;
		}
		scanf("%s",s2);
		int m=0,pos=0,sum;
		for(i=0;i<len;i++)
		{
			if(s2[i]=='?') m++;
			else if(s2[i]=='+') addsum--;
			else subsum--;
		}
		if(addsum<0 || subsum<0)
			printf("%.9lf\n",0);
		else
		{
			if(addsum+subsum!=m)
				printf("%.9lf\n",0);
			else
			{
				double ans;
				ans=ipow(0.5,m)*C(addsum,m);
				printf("%.9lf\n",ans);
			}
		}
	}
	return 0;
}
/*
++++++++++
+++??++?++

--+++---+-
??????????

*/


Codeforces Round #272 (Div. 2) B. Dreamoon and WiFi (超几何分布)