Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include <map>
- #include <vector>
- #include <algorithm>
- // #include<bits/stdc++.h>
- using namespace std;
- const int INF = 1e8;
- typedef long long ll;
- vector<ll> v;
- map<pair<int, ll>, int> dp;
- map<pair<int, ll>, pair<int, ll> > backtrack;
- map<pair<int, ll>, ll> numbers_taken;
- int rec(int at, ll x) {
- if(x == 0) {
- return 0;
- }
- if(dp.count(make_pair(at, x))) {
- return dp[make_pair(at, x)];
- }
- int res = INF;
- int id = lower_bound(v.begin(), v.end(), x) - v.begin();
- if(id < 0 or id >= v.size()) {
- id = (int) v.size() - 1;
- }
- vector<pair<int, ll> > sorted_rec;
- for(int i = id; i >= max(0, id - 5); i--) {
- if(x - v[i] >= 0) {
- sorted_rec.push_back(make_pair(rec(i, x - v[i]) + 1, i));
- }
- }
- sort(sorted_rec.begin(), sorted_rec.end());
- res = sorted_rec[0].first;
- backtrack[make_pair(at, x)] = make_pair(sorted_rec[0].second, x - v[sorted_rec[0].second]);
- numbers_taken[make_pair(at, x)] = v[sorted_rec[0].second];
- return dp[make_pair(at, x)] = res;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- ll x;
- cin >> x;
- for(ll digit = 1; digit <= 9; digit++) {
- ll tmp = digit;
- for(int i = 0; i < 12; i++) {
- if(tmp <= x) {
- v.push_back(tmp);
- }
- tmp *= 10LL;
- tmp += digit;
- }
- }
- sort(v.begin(), v.end());
- int res = rec((int) v.size() - 1, x);
- for(int i = 0; i < (int) v.size(); i++) {
- for(ll j = 0; j <= 10; j++) {
- if(v[i] * j == x) {
- if(res > j) {
- cout << j << endl;
- for(int l = 0; l < j; l++) {
- cout << v[i] << " ";
- }
- return 0;
- }
- }
- }
- }
- cout << res << endl;
- pair<int, ll> at = make_pair((int) v.size() - 1, x);
- while(true) {
- if(at.second == 0) {
- break;
- }
- cout << numbers_taken[at] << " ";
- at = backtrack[at];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement