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

Re:一定要注意这两种情况

Posted by 00648057 at 2011-03-25 20:32:43 on Problem 1189
In Reply To:一定要注意这两种情况 Posted by:00648057 at 2011-03-25 20:31:46
#include <iostream>
using namespace std;

int N,M;
int map[60][120];
__int64 prob[60][120];

__int64 zg(__int64 a, __int64 b)
{
	while (b%a)
	{
		__int64 k = b%a;
		b = a;
		a = k;
	}
	return a;
}

int main()
{
	cin>>N>>M;
	
	for (int i=0; i<N; i++)
	{
		int start = N-i;
		char temp;
		for (int j=0; j<=i; j++)
		{
			do 
			{
				cin>>temp;
			} while (temp!='*' &&  temp!='.');
			
			if (temp == '*')
				map[i][start] = 1;
			start += 2;
		}	
	}
	for (int j=0; j<2*(N+1); j++)
		map[N][j] = 1;

	int first = 0;
	while (map[first][N] == 0)
		first ++;
	prob[first][N] = 1;
	for (int i=0; i<=N; i++)
		prob[first][N] *= 2;

	for (int i=0; i<N; i++)
		for (int j=N-i; j<=N+i; j+=2)
			if (map[i][j] == 1)
			{
				int bottom = i;
				while (map[bottom][j-1] == 0)
					bottom++;
				prob[bottom][j-1] += prob[i][j]/2;

				bottom = i;
				while (map[bottom][j+1] == 0)
					bottom++;
				prob[bottom][j+1] += prob[i][j]/2;
			}

	if (M>0)
		prob[N][2*M] += prob[N][2*M-1]/2;
	if (M<N)
		prob[N][2*M] += prob[N][2*M+1]/2;

	if (prob[N][2*M] == 0)
		cout << "0/1" <<endl;
	else
	{
		__int64 down = prob[first][N];
		__int64 up = prob[N][2*M];
		__int64 com = zg(up, down);
		cout << up/com << '/' << down/com <<endl;
	}

}

> 1.最上面一个钉子是空的
>      .
>    *  *
>   *  *  *
> 
> 
> 2.最后一行没有钉子
> 
> 球有可能落在两个空格中间的隔板上
> 
>      ×
>    * *
>   * * *
>  . * . *
> _|_|_|_|_

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