Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int maxn = 25;
- typedef long long ll;
- vector<int> v1, v2;
- ll dp[maxn][4][4][4];
- int sz;
- ll rek(int at, int max_digit, int min_digit, int has_started) {
- if(at == sz) {
- return (ll) has_started;
- }
- if(dp[at][max_digit][min_digit][has_started] != -1) {
- return dp[at][max_digit][min_digit][has_started];
- }
- ll res = 0LL;
- int tmp_min_digit = v1[at];
- if(min_digit) {
- tmp_min_digit = 0;
- }
- int tmp_max_digit = v2[at];
- if(max_digit) {
- tmp_max_digit = 9;
- }
- for(int i = tmp_min_digit; i <= tmp_max_digit; i++) {
- ll tmp = 1LL;
- int tmp_started = (has_started or i > 0);
- if(has_started or i > 0) {
- tmp = (ll) i;
- }
- int m1 = min_digit;
- if(min_digit == 0) {
- if(i > tmp_min_digit) {
- m1 = 1;
- }
- }
- int m2 = max_digit;
- if(max_digit == 0) {
- if(i < tmp_max_digit) {
- m2 = 1;
- }
- }
- res = max(res, rek(at + 1, m2 , m1, tmp_started) * tmp);
- }
- return dp[at][max_digit][min_digit][has_started] = res;
- }
- ll backtrack(int at, int max_digit, int min_digit, int has_started) {
- if(at == sz) {
- return has_started;
- }
- ll res = dp[at][max_digit][min_digit][has_started];
- int tmp_min_digit = v1[at];
- if(min_digit) {
- tmp_min_digit = 0;
- }
- int tmp_max_digit = v2[at];
- if(max_digit) {
- tmp_max_digit = 9;
- }
- for(int i = tmp_min_digit; i <= tmp_max_digit; i++) {
- ll tmp = 1LL;
- int tmp_started = (has_started or i > 0);
- if(has_started or i > 0) {
- tmp = (ll) i;
- }
- int m1 = min_digit;
- if(min_digit == 0) {
- if(i > tmp_min_digit) {
- m1 = 1;
- }
- }
- int m2 = max_digit;
- if(max_digit == 0) {
- if(i < tmp_max_digit) {
- m2 = 1;
- }
- }
- if(res == rek(at + 1, m2 , m1, tmp_started) * tmp) {
- if(tmp_started) {
- cout << i;
- }
- backtrack(at + 1, m2 , m1, tmp_started);
- break;
- }
- }
- return res;
- }
- int main(){
- ll a, b;
- cin >> a >> b;
- memset(dp, -1, sizeof dp);
- while(a) {
- v1.push_back(a % 10);
- a /= 10;
- }
- while(b) {
- v2.push_back(b % 10);
- b /= 10;
- }
- if(v1.size() < v2.size()) {
- while(v1.size() < v2.size()) {
- v1.push_back(0);
- }
- }
- if(v2.size() < v1.size()) {
- while(v2.size() < v1.size()) {
- v2.push_back(0);
- }
- }
- reverse(v1.begin(), v1.end());
- reverse(v2.begin(), v2.end());
- sz = max((int) v1.size(), (int) v2.size());
- rek(0, 0, 0, 0) ;
- backtrack(0, 0, 0, 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement