ZOJ - 2759

一、问题介绍 

 

Sample Input
 

13
35
 

Sample Output
 

-1
1 3 9

1
9 27

 

二、题解

可以考虑把物品质量用三进制表示，看看下表：

可以看出一个规律，即放置物品的方法和物品质量的三进制表示是有对应关系的，规律总结如下：

将M转为三进制。在转换过程中，
若某一位是0，不管；
若某一位是1，则在物品对面放一砝码，砝码质量是三进制该为的基数。
若某一位是2，则在物品同侧放一砝码，并且向前进位(m+=1)。

 

三、实现代码

#include <iostream>

using namespace std;

int main()
{
    int three[100];
    int n,Count,i;
    int box[21];
    while(cin>>n){
        for(i=0;i<100;i++)
            three[i]=0;
        i=0;
        Count=1;
        while(n/3!=0){
            three[i]=n%3;
            n=n/3;
            i++;
            Count++;
        }
        three[i]=n;

        int add=0;
        for(i=0;i<Count;i++){
            if(three[i]+add==2){
                three[i]=-1;
                add=1;
            }
            else if(three[i]+add==3){
                three[i]=0;
                add=1;
            }
            else{
                three[i]+=add;
                add=0;
            }
        }
        if(add==1){
            three[i]=1;
            Count++;
        }

        int tmp,weight,flag=0,startflag=0;
        for(i=0;i<Count;i++){
            tmp=i;
            weight=1;
            while(tmp--){
                weight*=3;
            }
            if(three[i]==-1){
                flag=1;
                if(startflag==0) cout<<weight;
                else cout<<" "<<weight;
                startflag=1;
            }
        }
        if(flag==0) cout<<-1<<endl;
        else cout<<endl;

        flag=0,startflag=0;
        for(i=0;i<Count;i++){
            tmp=i;
            weight=1;
            while(tmp--){
                weight*=3;
            }
            if(three[i]==1){
                flag=1;
                if(startflag==0) cout<<weight;
                else cout<<" "<<weight;
                startflag=1;
            }
        }
        if(flag==0) cout<<-1<<endl;
        else cout<<endl;

        cout<<endl;
    }
    return 0;
}

四、鸣谢

作者：tiaotiaoyly
原文：https://blog.csdn.net/tiaotiaoyly/article/details/2112754