http://bailian.openjudge.cn/practice/2248
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- An addition chain for n is an integer sequence with the following four properties:
- a0 = 1
- am = n
- a0 < a1 < a2 < ... < am-1 < am
- For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj
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<=n<=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.
Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
- 样例输入
5
7
12
15
77
0
- 样例输出
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
- 来源
- Ulm Local 1997