양팔 저울

당신에게 양팔 저울과 한 세트의 저울 추, 그리고 물건 하나가 주어져 있다. 저울추의 무게는 1, 3, 9, 27, 81, ... 즉 추의 무게는 3의 거듭 제곱이고, 각 정수 에 대하여 무게가 인 추가 정확히 하나 있다. 물건의 무게는 이고  은 양의 정수이다. 당신이 할 일은 물건을 양팔 저울의 왼쪽 접시에 올려놓고 저울추들을 한쪽 혹은 양쪽에 올려놓아 저울이 균형을 이루도록 하는 것이다. 물론 각각의 저울추는 어느 한쪽 접시에 올리거나 혹은 올리지 않을 수 있다.

다음과 같은 일을 하는 프로그램을 작성하고자 한다.

물건의 무게  을 입력 파일에서 읽고,

어떤 추를 저울의 왼쪽과 오른쪽 접시에 올려야 하는지 계산한 다음,

결과를 출력 파일에 쓴다.

물건의 무게 이 주어질 때, 어떤 추들을 저울의 왼쪽과 오른쪽 접시에 올려야 하는지 구하는 프로그램을 작성하시오.

프로그램 이름은 scale.cpp, 실행 파일의 이름은 scale.exe, 프로그램 설명 파일 이름은 scale.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 물건의 무게 이 주어진다. 단, 이다.

2004 가을학기 문제해결기법	문제 #8

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 출력 파일은 두 줄로 구성되어 있다. 첫째 줄에 왼쪽 접시에 올려놓은 추에 대한 정보를 출력한다. 맨 앞의 정수는 음이 아닌 정수로 왼쪽 접시에 올린 추의 개수이고 뒤이어 추의 무게를 증가하는 순서로 출력한다. 정수들 사이에는 빈칸을 하나 둔다. 둘째 줄은 첫째 줄과 같은 형식으로 오른쪽 접시에 올려놓은 추에 대한 정보를 출력한다.

입력과 출력의 예

입력(input.txt)

42

출력(output.txt)

3 3 9 27

1 81