2155. Addition Chains

单点时限: 2.0 sec

内存限制: 256 MB

An addition chain for $n$ is an integer sequence ${a_0, a_1,a_2,\ldots,a_m}$ with the following four properties:

  • $a_0 = 1$
  • $a_m = n$
  • $a_0 < a_1 < a_2 < \ldots < a_{m-1} < a_m$
  • For each $k$ ($1 \le k \le m$) there exist two (not necessarily different) integers $i$ and $j$ ($0 \le i, j \le k-1$) with $a_k = a_i + a_j$

You are given an integer $n$. Your job is to construct an addition chain for $n$ with minimal length. If there is more than one such sequence, any one is acceptable.

For example, ${1, 2, 3, 5}$ and ${1, 2, 4, 5}$ are both valid solutions when you are asked for an addition chain for $5$.

输入格式

The input will contain one or more test cases. Each test case consists of one line containing one integer $n$ ($1 \le n \le 100$). Input is terminated by a value of zero (0) for $n$.

输出格式

For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.

样例

Input
5
7
12
15
77
0
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

14 人解决,16 人已尝试。

20 份提交通过,共有 29 份提交。

3.9 EMB 奖励。

创建: 12 年前.

修改: 2 年,6 月前.

最后提交: 2 年,1 月前.

来源: Ulm Local 1997

题目标签