比赛 |
防止浮躁的小练习 |
评测结果 |
AAAAA |
题目名称 |
钉子和小球 |
最终得分 |
100 |
用户昵称 |
liuliuliu |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
0.37 MiB |
提交时间 |
2016-10-07 10:30:05 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long Euclid(long long x,long long y){
return y==0?x:Euclid(y,x%y);
}
class FRAC{
public:
long long a,b;//分子/分母
FRAC(){a=b=1;}
void output(void){cout<<a<<"/"<<b;}
void simp(void){
long long g=Euclid(a,b);
a/=g,b/=g;
}
};
bool operator < (FRAC x,FRAC y){
return x.a*y.b<x.b*y.a;
}
bool operator > (FRAC x,FRAC y){
return x.a*y.b>x.b*y.a;
}
bool operator != (FRAC x,FRAC y){
return x.a*y.b!=x.b*y.a;
}
bool operator == (FRAC x,FRAC y){
return x.a*y.b==x.b*y.a;
}
FRAC operator * (FRAC x,FRAC y){
x.a*=y.a,x.b*=y.b;
x.simp();
return x;
}
FRAC operator / (FRAC x,FRAC y){
x.a*=y.b,x.b*=y.a;
x.simp();
return x;
}
FRAC operator + (FRAC x,FRAC y){
long long lcm=Euclid(x.b,y.b);
lcm=x.b/lcm*y.b;
FRAC ans;
ans.b=lcm;
ans.a=x.a*(lcm/x.b)+y.a*(lcm/y.b);
ans.simp();
return ans;
}
FRAC operator - (FRAC x,FRAC y){
FRAC temp;
temp.b=x.b*y.b;
temp.a=x.a*y.b-x.b*y.a;
temp.simp();
return temp;
}
FRAC operator * (FRAC x,long long y){
x.a*=y;
x.simp();
return x;
}
FRAC operator / (FRAC x,long long y){
x.b*=y;
x.simp();
return x;
}
const int SIZEN=60;
int n,m;//n是规模,m是目标
//下标是1~n
FRAC p[SIZEN][SIZEN];
char board[SIZEN][SIZEN];
void read(void){
int i,j;
char ch;
scanf("%d%d",&n,&m);
FRAC one;one.a=one.b=1;
FRAC zero;zero.a=0,zero.b=1;
p[1][1]=one;
for(i=2;i<=n+1;i++){
for(j=1;j<=i;j++) p[i][j]=zero;
}
for(i=1;i<=n;i++){
j=1;
while(1){
ch=getchar();
if(ch=='*'||ch=='.') board[i][j++]=ch;
if(j>i) break;
}
}
}
void work(void){
int i,j;
FRAC temp;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
if(board[i][j]=='*'){//有钉子
temp=p[i][j];
temp=temp/2;
p[i+1][j]=p[i+1][j]+temp;
p[i+1][j+1]=p[i+1][j+1]+temp;
}
else{//无钉子
p[i+2][j+1]=p[i+2][j+1]+p[i][j];
}
}
}
p[n+1][m+1].output();
}
int main(){
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
read();
work();
return 0;
}