| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:一定要注意这两种情况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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator