시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 108 | 47 | 40 | 47.619% |
다음과 같은 네 가지 조건을 만족하는 자연수 수열 <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
Contest > University of Ulm Local Contest > University of Ulm Local Contest 1997 A번