Advertisement
Josif_tepe

Untitled

Feb 1st, 2024
747
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 KB | None | 0 0
  1. #include<iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <algorithm>  
  5. // #include<bits/stdc++.h>
  6. using namespace std;
  7. const int INF = 1e8;
  8. typedef long long ll;
  9. vector<ll> v;
  10. map<pair<int, ll>, int> dp;
  11. map<pair<int, ll>, pair<int, ll> > backtrack;
  12. map<pair<int, ll>, ll> numbers_taken;
  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.    
  21.     int res = INF;
  22.     int id = lower_bound(v.begin(), v.end(), x) - v.begin();
  23.     if(id < 0 or id >= v.size()) {
  24.         id = (int) v.size() - 1;
  25.     }
  26.     vector<pair<int, ll> > sorted_rec;
  27.     for(int i = id; i >= max(0, id - 5); i--) {
  28.         if(x - v[i] >= 0) {
  29.             sorted_rec.push_back(make_pair(rec(i, x - v[i]) + 1, i));
  30.         }
  31.     }
  32.     sort(sorted_rec.begin(), sorted_rec.end());
  33.     res = sorted_rec[0].first;
  34.     backtrack[make_pair(at, x)] = make_pair(sorted_rec[0].second, x - v[sorted_rec[0].second]);
  35.     numbers_taken[make_pair(at, x)] = v[sorted_rec[0].second];
  36.     return dp[make_pair(at, x)] = res;
  37. }
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     ll x;
  41.     cin >> x;
  42.    
  43.    
  44.     for(ll digit = 1; digit <= 9; digit++) {
  45.         ll tmp = digit;
  46.         for(int i = 0; i < 12; i++) {
  47.             if(tmp <= x) {
  48.                 v.push_back(tmp);
  49.             }
  50.             tmp *= 10LL;
  51.             tmp += digit;
  52.         }
  53.     }
  54.     sort(v.begin(), v.end());
  55.         int res =  rec((int) v.size() - 1, x);
  56.  
  57.     for(int i = 0; i < (int) v.size(); i++) {
  58.         for(ll j = 0; j <= 10; j++) {
  59.             if(v[i] * j == x) {
  60.                 if(res > j) {
  61.                     cout << j << endl;
  62.                     for(int l = 0; l < j; l++) {
  63.                         cout << v[i] << " ";
  64.                     }
  65.                     return 0;
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout << res << endl;
  71.     pair<int, ll> at = make_pair((int) v.size() - 1, x);
  72.     while(true) {
  73.         if(at.second == 0) {
  74.             break;
  75.         }
  76.         cout << numbers_taken[at] << " ";
  77.         at = backtrack[at];
  78.     }
  79.     return 0;
  80. }
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement