迭代加深搜索练习，中午复习时候用的。
http://oi.tju.edu.cn/problem/view/1108.html
#include
using namespace std;
const int N = 1001;
const int list[N] = {0,1,2,3,3,4,4,5,4,5,5,6,5,6,6,6,5,6,6,7,6,7,7,7,6,7,7,7,7,8,7,8,6,7,7,8,7,8,8,8,7,8,8,8,8,8,8,9,7,8,8,8,8,9,8,9,8,9,9,9,8,9,9,9,7,8,8,9,8,9,9,10,8,9,9,9,9,9,9,10,8,9,9,9,9,9,9,10,9,10,9,10,9,10,10,10,8,9,9,9,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,10,10,10,10,9,10,10,10,10,10,10,11,8,9,9,10,9,10,10,10,9,10,10,11,10,11,11,11,9,10,10,10,10,10,10,11,10,10,10,11,10,11,11,11,9,10,10,10,10,10,10,11,10,11,10,11,10,11,11,11,10,11,11,11,10,11,11,11,10,11,11,11,11,11,11,12,9,10,10,10,10,11,10,11,10,11,11,11,10,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,12,10,11,11,11,11,11,11,11,11,11,11,12,11,12,11,12,10,11,11,11,11,11,11,12,11,11,11,12,11,12,12,11,9,10,10,11,10,11,11,12,10,11,11,12,11,12,11,12,10,11,11,12,11,12,12,12,11,11,12,12,12,12,12,12,10,11,11,11,11,11,11,12,11,11,11,12,11,12,12,12,11,12,11,12,11,12,12,12,11,12,12,12,12,12,12,12,10,11,11,11,11,11,11,12,11,12,11,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,
12,12,12,13,12,12,12,13,10,11,11,11,11,12,11,12,11,12,12,12,11,12,12,12,11,12,12,12,12,12,12,13,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,12,12,13,11,12,12,12,12,12,12,13,12,12,12,13,12,13,13,12,11,12,12,12,12,12,12,12,12,12,12,12,12,13,12,13,12,13,12,13,12,13,13,13,12,13,13,13,12,13,13,13,11,12,12,12,12,12,12,13,12,12,12,13,12,13,13,12,12,13,12,13,12,13,13,13,12,13,13,13,13,13,12,13,10,11,11,12,11,12,12,13,11,12,12,13,12,13,13,13,11,12,12,13,12,13,13,13,12,13,13,13,12,13,13,13,11,12,12,13,12,13,13,13,12,12,13,13,13,13,13,13,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,11,12,12,12,12,12,12,13,12,12,12,13,12,13,13,13,12,13,12,13,12,13,13,13,12,13,13,13,13,13,13,14,12,13,13,13,12,13,13,13,12,13,13,13,13,13,13,13,12,13,13,13,13,13,13,13,13,13,13,14,13,13,13,13,11,12,12,12,12,12,12,13,12,13,12,13,12,13,13,13,12,13,13,13,12,13,13,13,12,13,13,13,13,13,13,14,12,13,13,13,13,13,13,13,12,13,13,13,13,13,13,13,12,13,13,13,13,13,13,14,13,13,13,13,13,14,13,14,12,13,13,13,13,13,13,13,13,13,13,13,
13,13,13,14,12,13,13,13,13
,13,14,13,13,13,13,13,14,13,13,12,13,13,13,13,13,13,14,13,13,13,13,13,13,13,14,13,14,13,14,13,14,14,13,13,14,13,14,13,13,14,14,11,12,12,12,12,13,12,13,12,13,13,13,12,13,13,13,12,13,13,13,13,14,13,14,12,13,13,13,13,14,13,14,12,13,13,13,13,13,13,14,13,13,13,14,13,13,14,13,12,13,13,13,13,14,13,14,13,13,13,14,13,14,13,14,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,14,13,13,13,14,13,14,14,14,13,14,13,14,13,14,14,14,12,13,13,13,13,13,13,14,13,13,13,14,13,14,14,13,13,14,13,14,13,14,14,14,13,14,14,13,14,14,13,14,12,13,13,13,13,13,13,13,13,13,13,14,13,14,13,14,13,14,13,14,13,14,13,14,13,14,14,14,13,14,14,14,13,14,14,14,13,14,14,14,13,14,14,14,14,14,14,14,13,14,14,14,14,14,14,14,13,14,14,14,14,14,14,14,12,13,13,13,13,13,13,14,13,13,13,14,13,14,14,13,13,14,13,14,13,14,14,14,13,14,14,14,14,14,13,14,13,14,14,14,13,14,14,14,13};
int a[N], an, n;
bool dfs(int k){
if (k==n) return a[n]==an;
for (int i=k;i>=1;i--){
a[k+1] = a[i] + a[k];
if (dfs(k+1)) return true;
}
return false;
}
void print(){
cout << n << endl;
for (int i=1;i<=n-1;i++)
cout << a[i] << " ";
cout << a[n] << endl;
}
int main(){
freopen("shulie.in", "r", stdin);
freopen("shulie.out", "w", stdout);
a[1] = 1;
cin >> an; n = list[an];
dfs(1); print();
}
