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
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <cassert>
#define NDEBUG

using namespace std;

const int MAX_VOL = 120206;
const int MAX_VOL_BITS = 17;
const int MAX_N = 1000000;

int count_bits(int a)
{
    assert(a>0);
    int count = 0;
    while(a)
    {
        count += a%2;
        a >>= 1;
    }
    return count;
}
int count_trailing_zeros(int a)
{
    assert(a>0);
    int count = 0;
    while(a%2==0)
    {
        ++count;
        a >>= 1;
    }
    return count;
}

int find_lowest(int number, int bit_power)
{
    assert(bit_power>0);
    assert(bit_power<=MAX_VOL_BITS);
    int actual_bits_count = count_bits(number);
    while(actual_bits_count > bit_power)
    {
        number += 1 << count_trailing_zeros(number);
        assert(actual_bits_count>=count_bits(number));
        actual_bits_count = count_bits(number);
        
    }
    if( actual_bits_count < bit_power )
    {
        int bit_mask = 1;
        for(int i=0; i<MAX_VOL_BITS; ++i)
        {
            if( !(bit_mask & number) )
            {
                number |= bit_mask;
                ++actual_bits_count;
                if(actual_bits_count==bit_power)
                {
                    return number;
                }
            }
            bit_mask <<= 1;
        }
    }
    return number;
}

int next_i_bit_number[MAX_VOL+1][MAX_VOL_BITS+1];
int ms_vol[MAX_N+1]; // ms_vol[i]: most significant (first) volume value of "bit power" i
int nexts[MAX_N+1];
int lengths[MAX_N+1];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0; i<=MAX_VOL; ++i)
    {
        for(int b=1; b<=MAX_VOL_BITS; ++b)
        {
            next_i_bit_number[i][b] = find_lowest(i+1, b);
        }
    }
    ms_vol[0] = 0;
    ms_vol[1] = 1;
    nexts[0] = 0;
    nexts[1] = 0;
    lengths[0] = 0;
    lengths[1] = 1;
    
    for(int i=2; i<=n; ++i)
    {
        int lowest = MAX_VOL+1;
        int next = 0;
        for(int v=1; v<=min(i,17); ++v)
        {
            int new_lowest = next_i_bit_number[ms_vol[i-v]][v];//find_lowest(ms_vol[i-v]+1, v);
            assert(new_lowest>=0);
            if(new_lowest < lowest )
            {
                lowest = new_lowest;
                next = i-v;
            }
        }
        ms_vol[i] = lowest;
        nexts[i] = next;
        lengths[i] = 1 + lengths[next];
    }
    
    cout << lengths[n] << "\n";
    int pos = n;
    //int total_bits = count_bits(ms_vol[pos]);
    cout << ms_vol[pos];
    pos = nexts[pos];
    while(pos!=0)
    {
        cout << " " << ms_vol[pos];
        //total_bits += count_bits(ms_vol[pos]);
        pos = nexts[pos];
    }
    cout << "\n";
    //cerr << "total number of bits=" << total_bits << endl;
    return 0;
}