比赛 防止浮躁的小练习 评测结果 AAAAA
题目名称 钉子和小球 最终得分 100
用户昵称 lingyixiaoyao 运行时间 0.002 s
代码语言 C++ 内存使用 0.38 MiB
提交时间 2016-10-07 10:18:06
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
int N,M,nail[60][60]={0};//1代表有,2代表无
LL gcd(LL a,LL b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
class miku//分数
{
public:
	LL a,b;//分子分母
	void print()
	{
		printf("%lld/%lld\n",a,b);
	}
	void yue()
	{
		if(a==0) b=1;
		else
		{
			LL tem;
			tem=gcd(a,b);
			while(tem!=1)
			{
				a/=tem;b/=tem;
				tem=gcd(a,b);
			}
		}
	}
	void operator /= (int c)
	{
		b*=c;
		yue();
    }
	void operator += (miku c)
	{	
		a=(LL)a*c.b;
		yue();
		a+=(LL)c.a*b;
		yue();
		b*=c.b;
		yue();
	}
}G[60][60];
void DP()
{
	miku tem;
	miku zero;
	zero.a=0;zero.b=1;
	//zero.print();
	for(int i=1;i<=N+1;i++) for(int j=1;j<=i;j++) G[i][j]=zero;
	G[1][1].a=G[1][1].b=1;
	//G[1][1].print();
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
		{
			//cout<<i<<" "<<j<<" ";
			//G[i][j].print();
			if(nail[i][j]==1)
			{
				tem=G[i][j];
				tem/=2;
				//tem.print();
				G[i+1][j]+=tem;
				G[i+1][j+1]+=tem;
			}
			else
			{
				G[i+2][j+1]+=G[i][j];
			}
		}
	G[N+1][M+1].print();
}
int main()
{
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		char str[2];
		int tot=0;
		while(1)
		{
			tot++;
		if(tot>i) break;
		scanf("%s",str);
		if(str[0]=='*')
		nail[i][tot]=1;
		else if(str[0]=='.') nail[i][tot]=2;
		else cout<<"error"<<endl;
		}
	}
	DP();
	return 0;
}