Problem #2155 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

An addition chain for $n$ is an integer sequence $a_{0}, a_{1}, a_{2}, \dots, a_{m}$ with the following four properties:

$a_{0} = 1$
$a_{m} = n$
$a_{0} < a_{1} < a_{2} < \dots < a_{m - 1} < a_{m}$
For each $k$ ( $1 \leq k \leq m$ ) there exist two (not necessarily different) integers $i$ and $j$ ( $0 \leq i, j \leq 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 \leq n \leq 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

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

17 人解决，19 人已尝试。

23 份提交通过，共有 36 份提交。

3.7 EMB 奖励。

创建: 16 年，10 月前.

修改: 7 年，3 月前.

最后提交: 1 月，1 周前.

来源: Ulm Local 1997

construction

2155. Addition Chains

输入格式

输出格式

样例

服务

开源

关于我们