POJ 1702 Eva's Balance

Eva's Balance
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 2889
 
Accepted: 1424
Description
Eva has a balance with 20 poises. The weights of the poises are 1, 3, 9, 27,...,3^19. Eva asserts that she has a way to measure any object whose weight is an integer from 1 to (3^20-1)/2. Assuming that Eva has placed an object with the weight in this range on the left tray of the balance, your task is to place the proper poises on the proper trays so as to weigh the object out.
Input
The first line is an integer T (1 <= T <= 20), which shows the number of the test cases. Each of the following T lines contains an integer W (1 <= W <= (3^20-1)/2), expressing the weight of an object.
Output
For each test case print a line, showing the weights of the poises on the left tray and the right tray. Use a space to separate the left tray and the right tray. The poises on the same tray are arranged in the increasing order, and a comma separates every two of them. If there is no poise on the tray, output "empty".
Sample Input

3
9
5
20

Sample Output

empty 9
1,3 9
1,9 3,27

Source
POJ Monthly--2004.07.18 
 
/* 먼저 입력수num을 3진법 티나리로 변환한 다음에 낮은 위치에서 높은 위치로 3진법을 처리합니다. 티나리[i]의 값은 네 가지 가능성이 있습니다. 1) 0, 건너뛰기 2) 1, 3^i를 오른쪽 서열 2) 2, 3^i를 왼쪽 서열에 넣고 티나리[i+1]+3)3을 티나리[i+1]++;왜 표시할 수 있는 최대수(3^20-1)/2는 모두 20자리이기 때문에 최대는 전체 1의 수만 표시할 수 있다. 20개의 1이 이미 가장 크다. 임의의 위치에 1을 더하면 20자리를 초과하여 표시해야 한다. 등비수열을 활용하여 합쳐서 표시할 수 있는 최대수는 (3^20-1)/2*/#include #define MAX_N 20 int expv[MAX_N + 1]; int tinary[MAX_N + 1]; int left[MAX_N + 1]; int right[MAX_N + 1]; int lnum, rnum; int getTinary(int n) { int quotient = n, len = 0; while(quotient != 0) { tinary[len++] = quotient % 3; quotient/= 3; } return len; } void getPos(int n) { lnum = rnum = 0; memset(tinary, 0, sizeof(tinary)); int p, len = getTinary(n); for(p = 0; p < len; p++) { if(tinary[p] == 1) right[rnum++] = expv[p]; else if(tinary[p] == 2) { left[lnum++] = expv[p]; tinary[p + 1]++; } else if(tinary[p] == 3) tinary[p + 1]++; } if(tinary[len] == 1) right[rnum++] = expv[len]; if(lnum == 0) printf("empty"); else { for(p = 0; p < lnum; p++) { if(p != 0) printf(","); printf("%d", left[p]); } } printf(""); if(rnum == 0) printf("empty"); else { for(p = 0; p < rnum; p++)  { if(p != 0) printf(","); printf("%d", right[p]); } } printf("/n"); } int main() { int caseN, i; expv[0] = 1; for(i = 1; i < MAX_N; i++) expv[i] = expv[i - 1] * 3; scanf("%d", &caseN); int num; while(caseN--) { scanf("%d", &num); getPos(num); } return 0; }