1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

int dp[1000100];
int n;

vector<int> vec[20];

int get_next(int x, int bt) {
    auto it = upper_bound(vec[bt].begin(), vec[bt].end(), x);
    if (it == vec[bt].end())
        return -1;
    return *it;
}

void solve() {
    cin >> n;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        vec[__builtin_popcount(i)].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < 20; j++) {
            if (i-j < 0)
                break;
            int x = dp[i-j];
            int y = get_next(x, j);
            if (y != -1 && y < dp[i]) {
                dp[i] = y;
            }
        }
    }
    vector<int> ansvec;
    while(n) {
        ansvec.push_back(dp[n]);
        n -= __builtin_popcount(dp[n]);
    }
    cout << ansvec.size() << "\n";
    for (int x : ansvec)
        cout << x << ' ';
    cout << "\n";
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    t = 1;

    #ifdef Local
        // freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        // cin >> t;
    #endif
    // cin >> t;
    
    while(t--){
        solve();
    }


    return 0;
}