Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个

Posted by lzy_Dennis at 2023-09-14 21:51:43 on Problem 1189
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int N = 55;

long long gcd(long long a, long long b) {
	if(a < b) {
		a = a^b;
		b = a^b;
		a= a^b;
	}
	long long tmp  = 0;
	while((tmp = a % b) != 0) {
		a = b;
		b = tmp;
	}
	return b;
}
int main() {
	char triangle[N][N];
	int n,m;
	cin>>n>>m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= i; j++) {
			cin>>triangle[i][j];
		}
	}

	long long dp[N][N];
	memset(dp,0,sizeof(dp));

	dp[0][0] = (long long)1 << n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j <=i; j++) {
			if(triangle[i][j] == '*') {
				dp[i+1][j] += dp[i][j] >> 1;
				dp[i+1][j+1] += dp[i][j] >> 1;
			} else {
				dp[i+2][j+1]  += dp[i][j];
			}
		}
	}

	long long num = gcd(dp[n][m],(long long)1<<n);
	cout<<dp[n][m]/num<<"/"<<((long long)1<<n)/num<<endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator