Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <map>
- using namespace std;
- typedef long long ll;
- ll X;
- vector<ll> v;
- map<pair<ll, int> , short> m;
- vector<ll> v5;
- map<pair<int, ll>, pair<int, ll> > backtrack;
- map<pair<int, ll>, ll> broj;
- short rek(int at, ll L) {
- if(L == 0) {
- return 0;
- }
- if(m.count(make_pair(L, at))) {
- return m[make_pair(L, at)];
- }
- int r = 150;
- int id = lower_bound(v.begin(), v.end(), L) - v.begin();
- if(id >= v.size()) {
- id = (int) v.size() - 1;
- }
- if(id < v.size()) {
- vector<pair<int, int> > sorted;
- for(int x = id; x >= max(0, id - 5); x--){
- if(L - v[x] >= 0) {
- sorted.push_back(make_pair(rek(x, L - v[x]) + 1, x));
- }
- }
- sort(sorted.begin(), sorted.end());
- r = sorted[0].first;
- backtrack[make_pair(at, L)] = make_pair(sorted[0].second, L - v[sorted[0].second]);
- broj[make_pair(at, L)] = v[sorted[0].second];
- }
- return m[make_pair(L, at)] = r;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> X;
- for(int i = 1; i <= 9; i++) {
- ll num = 0;
- for(int j = 1; j <= 11; j++) {
- num = (num * 10LL) + i;
- if(num <= X) {
- v.push_back(num);
- }
- v5.push_back(100);
- }
- v5.push_back(100);
- }
- v5.push_back(100);
- sort(v.begin(), v.end());
- cout << rek((int) v.size() - 1, X) << endl;
- pair<int, ll> at = make_pair((int) v.size() - 1, X);
- while(true) {
- if(at.second == 0) {
- break;
- }
- // cout << at.first << " " << at.second << endl;
- cout << broj[at] << " ";
- at = backtrack[at];
- }
- return 0;
- }
- // 99123959998
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement