Time Limit: 1s
Memory Limit: 128MB
3의 지수승 꼴인 수들을 원소로 가진 집합 S를 생각해보자.
S = {1, 3, 9, 27, 81, 243, 729, ... }
이 S집합의 부분집합들에 대해서 부분집합의 원소들의 합을 구할 수 있을 것이다. 이 합의 크기가 오름차순이 되도록 부분집합들을 정렬했을 때 n번째에 위치하게 되는 부분집합을 구해보자. 공집합은 { }로 표기한다.
입력으로 여러 테스트데이터가 들어올 수 있다.
각 테스트데이터마다 한줄씩 자연수 n이 주어진다. (64bit signed int 범위 이내)
0이 들어온 경우 프로그램을 종료한다.
각 테스트데이터마다 n번째 부분집합을 한줄에 출력한다. 출력양식은 아래 sample output을 참조한다.
1 7 14 783 1125900981634049 0
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }