CUC-SUMMER-11-D

D - The least round way

Codeforces Beta Round #2

There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

starts in the upper left cell of the matrix;
each following cell is to the right or down from the current cell;
the way ends in the bottom right cell.
Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Example
Input
3
1 2 3
4 5 6
7 8 9
Output
0
DDRR

题意：一个n x n矩阵，从(1,1)到(n,n)使路径上所有数字乘积末尾的0数量最少，要怎么走

解法：末尾有0只能是2^a*5b*c形成，0的数量为2的数量和5的数量的最小值，所以求出到达路径上每个点时最小经过多少2以及最少经过多少5，单独考虑有0的情况

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int a[1005][1005][2];
bool b[1005][1005][2];
int dp[1005][1005][2];
int main()
{
    int n,x,flag=0,fx,fy;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&x);
            a[i][j][0]=0;
            a[i][j][1]=0;
            if(x==0){
                flag=1;
                fx=i;
                fy=j;
                a[i][j][0]=1;
                a[i][j][1]=1;
                continue;
            }
            while(x%2==0){
                a[i][j][0]++;
                x/=2;
            }
            while(x%5==0){
                a[i][j][1]++;
                x/=5;
            }
        }
    }
    for(int k=0;k<2;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int ans=INT_MAX;
                if(i==0&&j==0)
                    ans=0;
                if(i!=0&&dp[i-1][j][k]<ans){
                    ans=dp[i-1][j][k];
                }
                if(j!=0&&dp[i][j-1][k]<ans){
                    ans=dp[i][j-1][k];
                    b[i][j][k]=1;
                }
                dp[i][j][k]=ans+a[i][j][k];
            }
        }
    }
    int k;
    if(dp[n-1][n-1][0]>dp[n-1][n-1][1])
        k=1;
    else
        k=0;
    if(flag==1&&dp[n-1][n-1][k]>1){
        cout<<1<<endl;
        for(int i=0;i<fx;i++)
            cout<<"D";
        for(int i=0;i<fy;i++)
            cout<<"R";
        for(int i=fx;i<n-1;i++)
            cout<<"D";
        for(int i=fy;i<n-1;i++)
            cout<<"R";
    }
    else{
        string s;
        int i=n-1,j=n-1;
        while(i||j){
            if(b[i][j][k]==1){
                s+="R";
                j--;
            }
            else{
                s+="D";
                i--;
            }
        }
        reverse(s.begin(),s.end());
        cout<<dp[n-1][n-1][k]<<endl<<s<<endl;
    }
}