Advertisement
Josif_tepe

Untitled

Nov 15th, 2023
631
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 25;
  5. typedef long long ll;
  6.  
  7. vector<int> v1, v2;
  8. ll dp[maxn][4][4][4];
  9. int sz;
  10. ll rek(int at, int max_digit, int min_digit, int has_started) {
  11.     if(at == sz) {
  12.         return (ll) has_started;
  13.     }
  14.     if(dp[at][max_digit][min_digit][has_started] != -1) {
  15.         return dp[at][max_digit][min_digit][has_started];
  16.     }
  17.     ll res = 0LL;
  18.    
  19.     int tmp_min_digit = v1[at];
  20.     if(min_digit) {
  21.         tmp_min_digit = 0;
  22.     }
  23.     int tmp_max_digit = v2[at];
  24.     if(max_digit) {
  25.         tmp_max_digit = 9;
  26.     }
  27.    
  28.     for(int i = tmp_min_digit; i <= tmp_max_digit; i++) {
  29.         ll tmp = 1LL;
  30.         int tmp_started = (has_started or i > 0);
  31.         if(has_started or i > 0) {
  32.             tmp = (ll) i;
  33.         }
  34.         int m1 = min_digit;
  35.         if(min_digit == 0) {
  36.             if(i > tmp_min_digit) {
  37.                 m1 = 1;
  38.             }
  39.         }
  40.         int m2 = max_digit;
  41.         if(max_digit == 0) {
  42.             if(i < tmp_max_digit) {
  43.                 m2 = 1;
  44.             }
  45.         }
  46.         res = max(res, rek(at + 1, m2 , m1, tmp_started) * tmp);
  47.     }
  48.     return dp[at][max_digit][min_digit][has_started] = res;
  49. }
  50.  
  51. ll backtrack(int at, int max_digit, int min_digit, int has_started) {
  52.     if(at == sz) {
  53.         return has_started;
  54.     }
  55.    
  56.     ll res = dp[at][max_digit][min_digit][has_started];
  57.    
  58.     int tmp_min_digit = v1[at];
  59.     if(min_digit) {
  60.         tmp_min_digit = 0;
  61.     }
  62.     int tmp_max_digit = v2[at];
  63.     if(max_digit) {
  64.         tmp_max_digit = 9;
  65.     }
  66.    
  67.     for(int i = tmp_min_digit; i <= tmp_max_digit; i++) {
  68.         ll tmp = 1LL;
  69.         int tmp_started = (has_started or i > 0);
  70.         if(has_started or i > 0) {
  71.             tmp = (ll) i;
  72.         }
  73.         int m1 = min_digit;
  74.         if(min_digit == 0) {
  75.             if(i > tmp_min_digit) {
  76.                 m1 = 1;
  77.             }
  78.         }
  79.         int m2 = max_digit;
  80.         if(max_digit == 0) {
  81.             if(i < tmp_max_digit) {
  82.                 m2 = 1;
  83.             }
  84.         }
  85.        
  86.         if(res == rek(at + 1, m2 , m1, tmp_started) * tmp) {
  87.        
  88.             if(tmp_started) {
  89.                 cout << i;
  90.                
  91.             }
  92.             backtrack(at + 1, m2 , m1, tmp_started);
  93.             break;
  94.         }
  95.     }
  96.     return res;
  97. }
  98. int main(){
  99.     ll a, b;
  100.     cin >> a >> b;
  101.     memset(dp, -1, sizeof dp);
  102.     while(a) {
  103.         v1.push_back(a % 10);
  104.         a /= 10;
  105.     }
  106.     while(b) {
  107.         v2.push_back(b % 10);
  108.         b /= 10;
  109.     }
  110.     if(v1.size() < v2.size()) {
  111.         while(v1.size() < v2.size()) {
  112.             v1.push_back(0);
  113.         }
  114.     }
  115.     if(v2.size() < v1.size()) {
  116.         while(v2.size() < v1.size()) {
  117.             v2.push_back(0);
  118.         }
  119.     }
  120.     reverse(v1.begin(), v1.end());
  121.     reverse(v2.begin(), v2.end());
  122.     sz = max((int) v1.size(), (int) v2.size());
  123.    
  124.     rek(0, 0, 0, 0) ;
  125.     backtrack(0, 0, 0, 0);
  126.     return 0;
  127. }
  128.  
  129.  
  130.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement