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
// Mikołaj Gazeel
// I Liceum im. Bartłomieja Nowodworskiego w Krakowie

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef char i8;
typedef unsigned char u8;
typedef short i16;
typedef unsigned short u16;
typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef float f32; // Dont use plox
typedef long double f64;
 
#define arr array
#define vt vector
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define pqueue priority_queue

#define pb push_back
#define eb emplace_back

using namespace std; 

#define st first
#define nd second

#define not_divine_intellect  std::ios_base::sync_with_stdio(false); cin.tie(0)
#define satori i32 __val; cin >> __val; while(__val--)
#define rep(__val) for(i32 __temp = 0; __temp < __val; __temp++)

namespace std {
  template<typename T, typename U>
  ostream& operator<<(ostream &stream, const pair<T,U> &rhs) {
    return stream << '(' << rhs.st << ", " << rhs.nd << ')';
  }
}

#define mt make_tuple
#define mp make_pair

#define all(__arr) __arr.begin(), __arr.end()

constexpr i64 bandit = 14206902137;


#define DEBUG

i32 main() {
  not_divine_intellect;

  i32 n;
  cin >> n;

  vt<i32> dp(n+1, INT_MAX);
  vt<i32> dp2(n+1, -1);
  dp[0] = 0;
  dp2[0] = -1;

  for(i32 i = 1; i <= n; i++) {
    for(i32 j = 1; (j < 20) && (i-j >= 0); j++) {
      if(dp[i-j]+20 < (1 << j))
        continue;
      
      for(i32 k = dp[i-j]+1; k < dp[i-j]+3; k++) {
        if(__builtin_popcount(k) == j) {
          if(dp[i] > k){
            dp[i] = k;
            dp2[i] = i-j;
          }
        }
      }
    }
  }
  
  vt<i32> res;

  i32 i = n;
  while(i != 0) {
    res.push_back(dp[i]);
    i = dp2[i];
  }

  cout << res.size() << '\n';

  for(auto x : res)
    cout << x << ' ';

  cout << '\n';
}