3471. [POJ 2248]加成序列

【题目描述】

满足如下条件的序列 $X$（序列中元素被标号为：$1、2、3…m$）被称为“加成序列”：

$1、X[1]=1$

$2、X[m]=n$

$3、X[1]<X[2]<…<X[m-1]<X[m]$

$4、$对于每个 $k（2≤k≤m）$ 都存在两个整数 $i$ 和 $j$ （$1≤i,j≤k−1，i$ 和 $j$ 可相等），使得 $X[k]=X[i]+X[j]$。

你的任务是：给定一个整数 $n$，找出符合上述条件的长度 $m$ 最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

【输入格式】

输入包含多组测试用例。

每组测试用例占据一行，包含一个整数 $n$。

当输入为单行的 $0$ 时，表示输入结束。

【输出格式】

对于每个测试用例，首先输入满足需求的序列最小长度，然后输出该序列，数字之间用空格隔开。

每个输出占一行。

【样例输入】

5
7
12
15
77
0

【样例输出】

4 1 2 4 5
5 1 2 4 6 7
5 1 2 4 8 12
6 1 2 4 5 10 15
9 1 2 4 8 9 17 34 68 77

【数据范围】

$1\leq N\leq 100$

【来源】

《算法竞赛进阶指南》