Advertisement
Josif_tepe

Untitled

Mar 14th, 2022
844
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;
  6. typedef long long ll;
  7. ll X;
  8. vector<ll> v;
  9. map<pair<ll, int> , short> m;
  10. vector<ll> v5;
  11. map<pair<int, ll>, pair<int, ll> > backtrack;
  12. map<pair<int, ll>, ll> broj;
  13. short rek(int at, ll L) {
  14.     if(L == 0) {
  15.    
  16.         return 0;
  17.     }
  18.     if(m.count(make_pair(L, at))) {
  19.         return m[make_pair(L, at)];
  20.     }
  21.     int r = 150;
  22.     int id = lower_bound(v.begin(), v.end(), L) - v.begin();
  23.     if(id >= v.size()) {
  24.         id = (int)  v.size() - 1;
  25.     }
  26.     if(id < v.size()) {
  27.         vector<pair<int, int> > sorted;
  28.     for(int x = id; x >= max(0, id - 5); x--){
  29.         if(L - v[x] >= 0) {
  30.             sorted.push_back(make_pair(rek(x, L - v[x]) + 1, x));
  31.         }
  32.     }
  33.         sort(sorted.begin(), sorted.end());
  34.         r = sorted[0].first;
  35.         backtrack[make_pair(at, L)] = make_pair(sorted[0].second, L - v[sorted[0].second]);
  36.         broj[make_pair(at, L)] = v[sorted[0].second];
  37.     }
  38.     return m[make_pair(L, at)] = r;
  39. }
  40. int main() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin >> X;
  43.     for(int i = 1; i <= 9; i++) {
  44.         ll num = 0;
  45.         for(int j = 1; j <= 11; j++) {
  46.             num = (num * 10LL) + i;
  47.             if(num <= X) {
  48.                 v.push_back(num);
  49.             }
  50.             v5.push_back(100);
  51.  
  52.         }
  53.         v5.push_back(100);
  54.     }
  55.     v5.push_back(100);
  56.    
  57.     sort(v.begin(), v.end());
  58.    
  59.     cout << rek((int) v.size() - 1, X) << endl;
  60.     pair<int, ll> at = make_pair((int) v.size() - 1, X);
  61.     while(true) {
  62.         if(at.second == 0) {
  63.             break;
  64.         }
  65. //        cout << at.first << " " << at.second << endl;
  66.         cout << broj[at] << " ";
  67.         at = backtrack[at];
  68.     }
  69.     return 0;
  70. }
  71.  
  72. // 99123959998
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement