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