시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 13 12 60.000%

문제

다음과 같은 네 가지 조건을 만족하는 자연수 수열 <a0, a1, ..., am>을 n에 대한 덧셈 체인이라고 한다.

1. a0 = 1
2. am = n
3. a0 < a1 < a2 < ... < am-1 < am
4. 각각의 k(1 ≤ k ≤ m)에 대해서, ak = ai + aj를 만족하는 두 자연수(같아도 됨) i와 j가 존재 (0 ≤ i, j ≤ k-1)

자연수 n이 주어졌을 때, 가장 길이가 짧은 n에 대한 덧셈 체인을 찾는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 자연수 n이 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. (1 ≤ n ≤100)

출력

각각의 테스트 케이스에 대해서, 해당하는 덧셈 체인을 공백으로 구분하여 한 줄에 출력한다. 가능한 덧셈 체인이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력

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

힌트