Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1000 + 10 ;
- const int INF = -1u/4 ;
- int n ;
- int a[MAXN][MAXN][2];
- int DP[MAXN][MAXN][2];
- vector<char> s ;
- bool mee0 ;
- int x0,y0;
- int main()
- {
- cin >> n;
- for(int i = 0 ; i < n ; i ++)
- for(int j = 0 ; j < n ; j ++){
- int x;
- scanf("%d",&x);
- if(x == 0){
- mee0 = true ;
- a[i][j][0] = a[i][j][1] = INF ;
- x0 = i ;
- }
- else{
- while(x%2 == 0){
- x/= 2 ;
- a[i][j][0] ++;
- }
- while(x%5 == 0){
- x/= 5 ;
- a[i][j][1] ++ ;
- }
- }
- DP[i][j][0] = DP[i][j][1] = INF ;
- for(int t = 0 ; t < 2 ; t ++){
- if(i == 0 && j == 0) {
- DP[i][j][t] = a[i][j][t];
- continue ;
- }
- if(i != 0) DP[i][j][t] = min (DP[i][j][t] , DP[i-1][j][t]);
- if(j != 0) DP[i][j][t] = min (DP[i][j][t] , DP[i][j-1][t]);
- DP[i][j][t] += a[i][j][t];
- }
- }
- int x ;
- if(DP[n-1][n-1][0] < DP[n-1][n-1][1])x = 0 ;
- else x = 1 ;
- int nx = n-1 , ny = n-1 ;
- if(mee0 && DP[n-1][n-1][x] >= 1){
- cout << "1" <<endl;
- for(int i = 0 ; i <x0 ; i ++) printf("D");
- for(int j = 0 ; j < n-1 ; j ++) printf("R");
- for(int i = x0 ; i < n-1 ; i ++ )printf("D");
- return 0 ;
- }
- while(nx != 0 || ny != 0){
- if(nx == 0){ny -- ; s.emplace_back('R') ; continue ;}
- else if(ny == 0){nx -- ; s.emplace_back('D') ; continue ;}
- else if(DP[nx-1][ny][x] > DP[nx][ny-1][x]){ny -- ; s.emplace_back('R') ; continue ;}
- else {nx -- ; s.emplace_back('D') ; continue ;}
- }
- cout << DP[n-1][n-1][x]<<endl;
- for(int i = s.size()-1 ; i >= 0 ; i --)
- printf("%c",s[i]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement