fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. #define rep(b) for(ll i=0;i<b;++i)
  8. #define f(i,a,b) for(ll i=a;i<=b;++i)
  9. #define vl vector<ll>
  10. #define vp vector<pair<ll,ll>>
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define eb emplace_back
  13. #define pb push_back
  14. #define ia(a,n) \
  15. vector<ll> a(n); \
  16. f(i,0,n-1) cin >> a[i]
  17.  
  18. int g5(int a){
  19.     int c1 = 0;
  20.     if(a == 0) return 0;
  21.     while((a%5) == 0){
  22.         c1++;
  23.         a/=5;
  24.     }
  25.     return c1;
  26. }
  27.  
  28. int g2(int n){
  29.     int c = 0;
  30.     if(n == 0) return 0;
  31.     while((n%2) == 0){
  32.         c++;
  33.         n/=2;
  34.     }
  35.     return c;
  36. }
  37.  
  38. void ullu(vector<vector<int>>& dp){
  39.     string s = "";
  40.     int i=0, j=0, n = dp.size();
  41.     while(1){
  42.         if(i==n-1 && j==n-1) break;
  43.         if(i+1 == n) j++, s+='R';
  44.         else if(j+1 == n) i++, s+='D';
  45.         else if(dp[i+1][j] <= dp[i][j+1]) i++, s+='D';
  46.         else j++,s+='R';
  47.     }
  48.     cout<<dp[0][0]<<endl;
  49.     cout<<s<<endl;
  50. }
  51.  
  52.  
  53. void solve(){
  54.     int n;
  55.     cin>>n;
  56.     vector<vector<int>> a(n,vector<int>(n)), dp(n,vector<int>(n,INT_MAX)), dp1(n,vector<int>(n,INT_MAX)); //1 is for 5
  57.     bool sp = false, zi = -1, zj = -1;
  58.     for(int i=0; i<n; i++) for(int j=0; j<n; j++) {cin>>a[i][j];}
  59.  
  60. rep(n) f(j, 0, n-1) {
  61.     if(a[i][j] == 0) {
  62.         cout << i << " " << j << " " << a[i][j] << endl;
  63.         sp = true;
  64.         zi = i;
  65.         zj = j;
  66.         cout << zi << " " << zj << endl;
  67.         break;
  68.     }
  69. }
  70.  
  71.  
  72.     dp[n-1][n-1] = g2(a[n-1][n-1]);
  73.     dp1[n-1][n-1] = g5(a[n-1][n-1]);
  74.  
  75.     for(int i=n-1; i>=0; i--){
  76.         for(int j=n-1; j>=0; j--){
  77.             if(i==n-1 && j==n-1) continue;
  78.             if(i+1 < n) dp[i][j] = min(dp[i][j] , g2(a[i][j]) + dp[i+1][j]);
  79.             if(j+1 < n) dp[i][j] = min(dp[i][j] , g2(a[i][j]) + dp[i][j+1]); 
  80.             if(i+1 < n) dp1[i][j] = min(dp1[i][j] , g5(a[i][j]) + dp1[i+1][j]);
  81.             if(j+1 < n) dp1[i][j] = min(dp1[i][j] , g5(a[i][j]) + dp1[i][j+1]); 
  82.         }
  83.     }
  84.  
  85.     cout<<a[zi][zj]<<endl;
  86.  
  87.     if(min(dp[0][0],dp1[0][0]) > 1 && sp){
  88.         cout<<1<<endl;
  89.         string s = "";
  90.         rep(zi) s+='D';
  91.         rep(zj) s+='R';
  92.         rep(n-1-zi) s+='D';
  93.         rep(n-1-zj) s+='R';
  94.         cout<<s<<endl;
  95.         return;
  96.     }
  97.  
  98.     if(dp[0][0] < dp1[0][0]) ullu(dp);
  99.     else ullu(dp1);
  100. }
  101.  
  102. int main() {
  103.   ios_base::sync_with_stdio(false);
  104.   cin.tie(NULL);
  105.   solve();
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin 
3
1 2 3
4 4 0
7 8 900
stdout 
1 2 0
1 1
4
1
DRDR
https://ideone.com/QbSuWL
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!