pku 1702簡單題，但思想很好。給定一些不同重量的砝碼，重為3^0, 3^1, ..., 3^19，要求用這些砝碼乘出物體的重量W，1 <= W <= (3^20-1)/2。
形式化的描述為：
給定W，以及砝碼重量
，求出集合
，使得
移項得
即系將W表示成一系列的3進制數(shù)的和或差。由于每個重量的砝碼只有一個，所以每個重量前面的系數(shù)只能是1，-1或0。首先將W表示為一般的3進制數(shù)，即系數(shù)允許為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 }