시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 18 17 60.714%

문제

다음과 같은 네 가지 조건을 만족하는 자연수 수열 <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)

출력

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

예제 입력 1

5
7
12
15
77
0

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6IjY1OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzNjdcdWMxNDggXHVjY2I0XHVjNzc4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjEyNCBcdWFjMDBcdWM5YzAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggXHVjMjE4XHVjNWY0ICZsdDthPHN1Yj4wPFwvc3ViPiwgYTxzdWI+MTxcL3N1Yj4sIC4uLiwgYTxzdWI+bTxcL3N1Yj4mZ3Q7XHVjNzQ0IG5cdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjM2N1x1YzE0OCBcdWNjYjRcdWM3NzhcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBhPHN1Yj4wPFwvc3ViPiA9IDE8YnIgXC8+XHJcbjIuIGE8c3ViPm08XC9zdWI+ID0gbjxiciBcLz5cclxuMy4gYTxzdWI+MDxcL3N1Yj4gJmx0OyBhPHN1Yj4xPFwvc3ViPiAmbHQ7IGE8c3ViPjI8XC9zdWI+ICZsdDsgLi4uICZsdDsgYTxzdWI+bS0xPFwvc3ViPiAmbHQ7IGE8c3ViPm08XC9zdWI+PGJyIFwvPlxyXG40LiBcdWFjMDFcdWFjMDFcdWM3NTggaygxICZsZTsgayAmbGU7IG0pXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgYTxzdWI+azxcL3N1Yj4gPSBhPHN1Yj5pPFwvc3ViPiArIGE8c3ViPmo8XC9zdWI+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4KFx1YWMxOVx1YzU0NFx1YjNjNCBcdWI0MjgpIGlcdWM2NDAgalx1YWMwMCBcdWM4NzRcdWM3YWMgKDAgJmxlOyBpLCBqICZsZTsgay0xKTxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzllN1x1Yzc0MCBuXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIzNjdcdWMxNDggXHVjY2I0XHVjNzc4XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzkwXHVjNWYwXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7MTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YjM2N1x1YzE0OCBcdWNjYjRcdWM3NzhcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YjM2N1x1YzE0OCBcdWNjYjRcdWM3NzhcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWRkaXRpb24gQ2hhaW5zIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBhZGRpdGlvbiBjaGFpbiBmb3IgbiBpcyBhbiBpbnRlZ2VyIHNlcXVlbmNlICZsdDthMCwgYTEsYTIsLi4uLGFtJmd0OyB3aXRoIHRoZSBmb2xsb3dpbmcgZm91ciBwcm9wZXJ0aWVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmE8c3ViPjA8XC9zdWI+ID0gMTxcL2xpPlxyXG5cdDxsaT5hPHN1Yj5tPFwvc3ViPiA9IG48XC9saT5cclxuXHQ8bGk+YTxzdWI+MDxcL3N1Yj4mbHQ7YTxzdWI+MTxcL3N1Yj4mbHQ7YTxzdWI+MjxcL3N1Yj4mbHQ7Li4uJmx0OyBhPHN1Yj5tLTE8XC9zdWI+Jmx0O2E8c3ViPm08XC9zdWI+PFwvbGk+XHJcblx0PGxpPkZvciBlYWNoIGsgKDEmbHQ7PWsmbHQ7PW0pIHRoZXJlIGV4aXN0IHR3byAobm90IG5lY2Nlc3NhcmlseSBkaWZmZXJlbnQpIGludGVnZXJzIGkgYW5kIGogKDAmbHQ7PWksIGombHQ7PWstMSkgd2l0aCBhPHN1Yj5rPFwvc3ViPj1hPHN1Yj5pPFwvc3ViPithPHN1Yj5qPFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYW4gaW50ZWdlciBuLiBZb3VyIGpvYiBpcyB0byBjb25zdHJ1Y3QgYW4gYWRkaXRpb24gY2hhaW4gZm9yIG4gd2l0aCBtaW5pbWFsIGxlbmd0aC4gSWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBzdWNoIHNlcXVlbmNlLCBhbnkgb25lIGlzIGFjY2VwdGFibGUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCAmbHQ7MSwyLDMsNSZndDsgYW5kICZsdDsxLDIsNCw1Jmd0OyBhcmUgYm90aCB2YWxpZCBzb2x1dGlvbnMgd2hlbiB5b3UgYXJlIGFza2VkIGZvciBhbiBhZGRpdGlvbiBjaGFpbiBmb3IgNS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHdpbGwgY29udGFpbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyIG4gKDEmbHQ7PW4mbHQ7PTEwMCkuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSB2YWx1ZSBvZiB6ZXJvICgwKSBmb3Igbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHJlcXVpcmVkIGludGVnZXIgc2VxdWVuY2UuIFNlcGFyYXRlIHRoZSBudW1iZXJzIGJ5IG9uZSBibGFuay48XC9wPlxyXG5cclxuPHA+SGludDogVGhlIHByb2JsZW0gaXMgYSBsaXR0bGUgdGltZS1jcml0aWNhbCwgc28gdXNlIHByb3BlciBicmVhayBjb25kaXRpb25zIHdoZXJlIG5lY2Vzc2FyeSB0byByZWR1Y2UgdGhlIHNlYXJjaCBzcGFjZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=