Addition Chains

题意翻译

## 题目描述 一个与 $n$ 有关的整数加成序列 $<a_0,a_1,a_2,...,a_m>$ 满足以下四个条件: $1.a_0=1$ $2.a_m=n$ $3.a_0<a_1<a_2<...<a_{m-1}<a_m$ $4.$ 对于每一个 $k(1≤k≤m)$ 都存在有两个整数 $i$ 和 $j(0≤i,j≤k-1,i$ 和 $j$ 可以相等 $)$ ,使得 $a_k=a_i+a_j$ 你的任务是:给定一个整数 $n$ ,找出符合上述四个条件的长度最小的整数加成序列。如果有多个满足要求的答案,只需要输出任意一个解即可。 举个例子,序列 $<1,2,3,5>$ 和 $<1,2,4,5>$ 均为 $n=5$ 时的解。 ## 输入格式 输入包含多组数据。每组数据仅一行包含一个整数 $n(1≤n≤10000)$ 。在最后一组数据之后是一个 $0$ 。 ## 输出格式 对于每组数据,输出一行所求的整数加成序列,每个整数之间以空格隔开。 感谢@Iowa_BattleShip 提供的翻译

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=470 [PDF](https://uva.onlinejudge.org/external/5/p529.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA529/0cf6e4f370f0135a68e11c531b88bafdcabeaddf.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA529/442cc11ac645016f32b2e5060d8cfc30396f272c.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA529/fe878da16d793f0355065ba06f2ba0e19c032631.png)

输入输出样例

输入样例 #1

5
7
12
15
77
0

输出样例 #1

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