比赛 |
防止浮躁的小练习 |
评测结果 |
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;
}