pku 1702简单题，但思想很好。给定一些不同重量的砝码，重为3^0, 3^1, ..., 3^19，要求用这些砝码乘出物体的重量W，1 <= W <= (3^20-1)/2。
形式化的描述为：
给定W，以及砝码重量
，求出集合
，使得
移项得
即系将W表示成一系列的3进制数的和或差。由于每个重量的砝码只有一个，所以每个重量前面的系数只能是1，-1或0。首先将W表示为一般的3进制数，即系数允许为0,1,2，再将这个式子改写为只含-1,0,1的式子，具体算法见下面的程序。
1 #include <iostream>
2
3 using namespace std;
4
5 long a[20];
6 int c[21];
7 long w;
8 void solve()
9 {
10 int i=19;
11 memset(c,0,sizeof(c));
12 while(w!=0)
13 {
14 c[i]=w/a[i];
15 w%=a[i--];
16 }
17 for(i=0;i<=19;i++)
18 {
19 if(c[i]==2)
20 {
21 c[i]=-1;
22 c[i+1]++;
23 }
24 else if(c[i]==3)
25 {
26 c[i]=0;
27 c[i+1]++;
28 }
29 }
30
31 //for(i=0;i<=19;i++) if(c[i]!=0) printf("%d ",c[i]*a[i]);
32 //printf("\n");
33 int flag=0;
34 for(i=0;i<=19;i++)
35 {
36 if(c[i]==-1 && flag==0){printf("%d",a[i]);flag=1;}
37 else if(c[i]==-1 && flag==1){printf(",%d",a[i]);}
38 }
39 if(flag==0) printf("empty");
40 printf(" ");
41 flag=0;
42 for(i=0;i<=19;i++)
43 {
44 if(c[i]==1 && flag==0) {printf("%d",a[i]);flag=1;}
45 else if(c[i]==1 && flag==1) printf(",%d",a[i]);
46 }
47 printf("\n");
48 return;
49 }
50
51 int main()
52 {
53 int i,j,k;
54 a[0]=1;
55 for(i=1;i<=19;i++) a[i]=3*a[i-1];
56 int t;
57 scanf("%d",&t);
58 while(t--)
59 {
60 scanf("%d",&w);
61 solve();
62 }
63 return 1;
64 }