# CFR 2 B. The least round way ( DP )

Problem - 2B - Codeforces

```int N;
vvi A;

void init(){
cin >> N;
A = vvi( N, vi( N ) );
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
cin >> A[ i ][ j ];
}

pii z_pos;
vvi dp2; // minimum count of 2s
vvi dp5;
vvp pre2;
vvp pre5;

int get2( int x ){
int res = 0;
while( x and x % 2 == 0 )
x /= 2,
++res;
return res;
}

int get5( int x ){
int res = 0;
while( x and x % 5 == 0 )
x /= 5,
++res;
return res;
}

map< pii, char > mpc;

void preprocess(){
mpc[ pii( 0, 1 ) ] = 'R';
mpc[ pii( 1, 0 ) ] = 'D';
z_pos = pii( -1, -1 );
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
if( A[ i ][ j ] == 0 )
z_pos = pii( i, j );
dp2 = dp5 = vvi( N, vi( N, INF ) );
pre2 = pre5 = vvp( N, vp( N, pii( -1, -1 ) ) );
dp2[ 0 ][ 0 ] = get2( A[ 0 ][ 0 ] );
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j ){
if( i + 1 < N and upmin( dp2[ i + 1 ][ j ], dp2[ i ][ j ] + get2( A[ i + 1 ][ j ] ) ) )
pre2[ i + 1 ][ j ] = pii( i, j );
if( j + 1 < N and upmin( dp2[ i ][ j + 1 ], dp2[ i ][ j ] + get2( A[ i ][ j + 1 ] ) ) )
pre2[ i ][ j + 1 ] = pii( i, j );
}
dp5[ 0 ][ 0 ] = get5( A[ 0 ][ 0 ] );
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j ){
if( i + 1 < N and upmin( dp5[ i + 1 ][ j ], dp5[ i ][ j ] + get5( A[ i + 1 ][ j ] ) ) )
pre5[ i + 1 ][ j ] = pii( i, j );
if( j + 1 < N and upmin( dp5[ i ][ j + 1 ], dp5[ i ][ j ] + get5( A[ i ][ j + 1 ] ) ) )
pre5[ i ][ j + 1 ] = pii( i, j );
}
}

void solve(){
if( not ( dp2[ N - 1 ][ N - 1 ] < dp5[ N - 1 ][ N - 1 ] ) )
swap( dp2, dp5 ),
swap( pre2, pre5 );
if( z_pos != pii( -1, -1 ) and dp2[ N - 1 ][ N - 1 ] > 1 ){
cout << 1 << endl;
for( int i = 0; i < z_pos.first; ++i )
cout << 'D';
for( int i = 0; i < z_pos.second; ++i )
cout << 'R';
for( int i = 0; i < N - 1 - z_pos.first; ++i )
cout << 'D';
for( int i = 0; i < N - 1 - z_pos.second; ++i )
cout << 'R';
cout << endl;
return;
}
cout << dp2[ N - 1 ][ N - 1 ] << endl;
stack< char > path;
for( int x = N - 1, y = N - 1; pre2[ x ][ y ] != pii( -1, -1 ); tie( x, y ) = pre2[ x ][ y ] )
path.push( mpc[ pii( x - pre2[ x ][ y ].first, y - pre2[ x ][ y ].second ) ] );
for( ; not path.empty(); path.pop() )
cout << path.top();
cout << endl;
}
```