Advertisement
Josif_tepe

Untitled

Mar 7th, 2024
594
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. vector<ll> v;
  9.  
  10. map<pair<int, ll>, int> dp;
  11. map<pair<int, ll>, pair<int, ll>> backtrack;
  12. map<pair<int, ll>, ll> number;
  13. int rec(int at, ll x) {
  14.     if(x == 0) {
  15.         return 0;
  16.     }
  17.     if(dp.count(make_pair(at, x))) {
  18.         return dp[make_pair(at, x)];
  19.     }
  20.     int res = 2e9;
  21.     int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
  22.     vector<pair<int, ll>> sorted_rec;
  23.     if(idx < 0 or idx >= v.size()) {
  24.         idx = v.size() - 1;
  25.     }
  26.     for(int i = idx; i >= max(0, idx - 6); i--) {
  27.         if(x - v[i] >= 0) {
  28.             sorted_rec.push_back(make_pair(rec(i, x - v[i]) + 1, i));
  29.         }
  30.     }
  31.     sort(sorted_rec.begin(), sorted_rec.end());
  32.     res = sorted_rec[0].first;
  33.     backtrack[make_pair(at, x)] = make_pair(sorted_rec[0].second, x - v[sorted_rec[0].second]);
  34.     number[make_pair(at, x)] = v[sorted_rec[0].second];
  35.    
  36.     return dp[make_pair(at ,x)] = res;
  37. }
  38.  
  39. int main()
  40. {
  41.     ll n;
  42.     cin >> n;
  43.    
  44.     for(int i = 1; i <= 9; i++) {
  45.         ll num = i;
  46.         for(int j = 0; j < 12; j++) {
  47.             if(num <= n) {
  48.                 v.push_back(num);
  49.             }
  50.             num = (num * 10) + i;
  51.         }
  52.     }
  53.     sort(v.begin(), v.end());
  54.     int ret =  rec(v.size() - 1, n);
  55.  
  56.     for(int i = 0; i < v.size(); i++) {
  57.         for(ll j = 0; j <= 20; j++) {
  58.             if(v[i]  *j == n) {
  59.                 if(ret > j) {
  60.                     cout << j << " ";
  61.                     for(int k =0 ; k < j; k++) {
  62.                         cout << v[i] << " ";
  63.                     }
  64.                     return 0;
  65.                 }
  66.             }
  67.         }
  68.     }
  69.     cout << ret << endl;
  70.     pair<int, ll> at = make_pair(v.size() - 1, n);
  71.     while(true) {
  72.         if(at.second == 0) {
  73.             break;
  74.         }
  75.         cout << number[at] << " ";
  76.         at = backtrack[at];
  77.     }
  78.     return 0;
  79. }
  80. // 2222222222
  81. // 22222222222
  82.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement