Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- using namespace std;
- 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> number;
- 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 = 2e9;
- int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
- vector<pair<int, ll>> sorted_rec;
- if(idx < 0 or idx >= v.size()) {
- idx = v.size() - 1;
- }
- for(int i = idx; i >= max(0, idx - 6); 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]);
- number[make_pair(at, x)] = v[sorted_rec[0].second];
- return dp[make_pair(at ,x)] = res;
- }
- int main()
- {
- ll n;
- cin >> n;
- for(int i = 1; i <= 9; i++) {
- ll num = i;
- for(int j = 0; j < 12; j++) {
- if(num <= n) {
- v.push_back(num);
- }
- num = (num * 10) + i;
- }
- }
- sort(v.begin(), v.end());
- int ret = rec(v.size() - 1, n);
- for(int i = 0; i < v.size(); i++) {
- for(ll j = 0; j <= 20; j++) {
- if(v[i] *j == n) {
- if(ret > j) {
- cout << j << " ";
- for(int k =0 ; k < j; k++) {
- cout << v[i] << " ";
- }
- return 0;
- }
- }
- }
- }
- cout << ret << endl;
- pair<int, ll> at = make_pair(v.size() - 1, n);
- while(true) {
- if(at.second == 0) {
- break;
- }
- cout << number[at] << " ";
- at = backtrack[at];
- }
- return 0;
- }
- // 2222222222
- // 22222222222
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement