5217: 「一本通 1.3 例 4」Addition Chains
[Creator : ]
Description
已知一个数列 $a_0, a_1, \dots, a_m$,其中 $a_0=1, a_m=n; a_0 < a_1 < a_2 < \dots < a_{m−1} < a_m$。
对于每个 $k\ (1 ≤ k ≤ m)$ 满足 $a_k=a_i+a_j\ (0 ≤ i, j ≤ k−1)$,这里 $i$ 与 $j$ 可以相等。
现给定 $n$ 的值,要求 $m$ 的最小值(并不要求输出)及这个数列的值(可能存在多个数列,只输出任意一个满足条件的就可以)。
对于每个 $k\ (1 ≤ k ≤ m)$ 满足 $a_k=a_i+a_j\ (0 ≤ i, j ≤ k−1)$,这里 $i$ 与 $j$ 可以相等。
现给定 $n$ 的值,要求 $m$ 的最小值(并不要求输出)及这个数列的值(可能存在多个数列,只输出任意一个满足条件的就可以)。
Input
多组数据,每行给定一个正整数 $n$。输入以 $0$ 结束。
Output
对于每组数据,输出满足条件的长度最小的数列。
Constraints
$1 \leq n \leq 100,\ 1 \leq k \leq m$
Sample 1 Input
5
7
12
15
77
0
Sample 1 Output
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77