1997/98 ACM International Collegiate Programming Contest

University of Ulm Local Contest
# Problem A

# Addition Chains

Source file: addition.(c|C|pas)

Input file: addition.in

An addition chain for *n* is an integer sequence *<a*_{0},
a_{1},a_{2},...,a_{m}> with the following
four properties:

*a*_{0} = 1
*a*_{m} = *n*
*a*_{0}<a_{1}<a_{2}<...<
a_{m-1}<a_{m}
- For each
*k* (1<=*k*<=*m*) there exist two
(not neccessarily different)
integers *i* and *j* (0<=*i*, *j*<=*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.
### Input Specification

The input file 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*.
### Output Specification

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.

### Sample Input

5
7
12
15
77
0

### Sample 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