문제1109--자라나라 나무나무

1109: 자라나라 나무나무

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

A 행성에는 "자라나라 나무나무" 라는 이름의 나무가 있습니다. 이 나무 씨앗은 목수들에게 아주 귀한 건축 재료 인데, 그 이유는 씨앗을 심은 다음 날, 무려 몸통의 길이가 1m인 나무가 되며, 그다음 날부터는 전날의 두 배의 길이가 되기 때문입니다. 단, 단점이 있다면 이러한 특징이 있는 만큼 매우 비싸며, 몸통이 매우 단단하여 자르는 비용이 상상을 초월한다는 점입니다. 그나마 다행인 건 몸통을 제외한 뿌리와 가지들을 자르는 건 쉽다는 점이지요.

하여튼, 이러한 성질 때문에 나무를 자르지 않고 이어 붙이는 방법으로 이 나무가 사용되고 있습니다.

예를 들어, 3m 길이의 기둥을 만들 때는 첫째 날에 나무 한 그루를 심고, 둘째 날에 나무 한 그루를 심습니다. 셋째 날에는 첫째 날 심은 나무는 2m 길이의 나무가 되고, 둘째 날 심은 나무는 1m 길이의 나무가 되어서, 두 개를 붙여 3m 길이의 나무 기둥을 만들 수 있습니다.

여러분은 이 목수를 도와, 되도록 적은 양의 나무 씨앗으로 길이 L의 기둥을 만드는 방법을 알려주려고 합니다.

L 길이의 나무를 만드는데, 몇 개의 씨앗과 몇 일째에 심으면 되는지 출력하는 프로그램을 만들어 주세요.


입력 설명

첫 줄에, 필요한 나무의 길이 L (1 <= L <= 1,000,000,000) 이 주어집니다.

출력 설명

첫째 줄에는 몇 개의 씨앗이 필요한지, 그다음 줄부터는 오름차순으로 몇 일째에 씨앗을 심어야 하는지 출력하고, 마지막 줄에는 나무를 베어야 하는 날을 출력해 주세요.

입력 예시 Copy

3

출력 예시 Copy

2
1
2
3

출처/분류