/*Eva's BalanceTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 3149 Accepted: 1564Description * 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 Input39520Sample Outputempty 91,3 91,9 3,27Source * POJ Monthly--2004.07.18 * 分析左侧砝码总重+物体重量＝右侧砝码总重物体重量＝右侧砝码总重-左侧砝码总重所以，问题可以转化为：给出正整数w，对3^i(0<=i<=19)加上权值s (s=-1,0或者1)，使得所有项的总 * 和为w。s=-1对应于砝码放在天平左侧，s=1对应于砝码放在天平右侧，s=0对应于不使用该砝码。 * 列举前10项的情形如下： * 1 3 9 27 .... * 0 0 0 0 0 .... * 1 +1 0 0 0 .... * 2 -1 +1 0 0 .... * 3 0 +1 0 0 .... * 4 +1 +1 0 0 .... * 5 -1 -1 +1 0 .... * 6 0 -1 +1 0 .... * 7 +1 -1 +1 0 .... * 8 -1 0 +1 0 .... * 9 0 0 +1 0 .... * 10 +1 0 +1 0 ....通过观察，这个表格和基数为3的“进位制”问题很像(如果对最基础的进位制问题的原理和方法不 * 清楚，建议先了解一下)。我们不妨定义映射f : {0,1,2}-->{0,1,-1}，即可将n%3的值相应 * 转换为这里所要求的权值。这里还有一个问题，除第一项以外，之后每一项的“第一个周期” * 都是不完全的，所以对迭代过程中的n=n/3要作一个修正，考察图中的5,6,7，这三个数的后 * 几项和2相同(红框所示)，所以迭代过程应该将5,6,7转换到2,同理2,3,4-->1，8,9,10-->3等 * 等，n=n/3最后修正为n=(n+1)/3。核心代码
index = 0;
int table[3] = {0,1,-1};
while (n) {
num[index] = table[n%3];
n = (n+1)/3;
index++;
} */
#include <cstdlib> #include <iostream> using namespace std; /* * */ int main(int argc, char** argv) { int t; cin>>t; while(t>0) { int n=0,m=0,i=0,a[21],b[21],s,table[3]={0,1,-1}, g[20]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441, 1594323,4782969,14348907,43046721,129140163,387420489,1162261467}; cin>>s; while(s) { if(table[s%3]<0)a[++n]=g[i]; if(table[s%3]>0)b[++m]=g[i]; s=(s+1)/3; ++i; } if(n>0) { i=0; while(++i<n)cout<<a[i]<<','; cout<<a[n]<<' '; } else cout<<"empty "; if(m>0) { i=0; while(++i<m)cout<<b[i]<<','; cout<<b[m]<<endl; } else cout<<"empty"<<endl; --t; } return 0; }
