题目描述

请了两位奆老来为自己种树，小X也稍稍有些不好意思了，于是他准备了一些零食和饮料来招待奆老们。
然而，小X有强迫症，他希望自己和好基友们所有的零食和饮料的质量都要完全相同。
由于小X是一个奆老，所以他看不起普通商店里卖的电子秤，他决定自己做一个。
他的称重工具是一架由金子制成的天平，这架天平的精度非常高，可以达到纳克的标准，1g=109ng，小X会把物品放在天平的右侧，然后在天平的左侧和右侧都放上一些砝码，直至天平平衡。该天平的砝码是用钻石制成的，每个砝码的质量依次为1ng、3ng、9ng、27ng、81ng……，每个砝码的质量都是3的幂次(如3的6次幂表示为3^6=729)，且各不相同。
由于小X是一个奆老，他有对各个物品未卜先知的能力，他会告诉你他的物品的质量，希望你给他一个方案，使得天平的两侧平衡。

 

输入

输入数据仅有一行包含一个正整数W，表示小X给出的物品的质量，重量单位是纳克(ng)

 

输出

输出数据共有两行，分别输出左右两端各个砝码及物体的质量，同一行砝码重量必须从小到大排序后按次序输出，第二行的第一个数必须先输出物体的质量，然后才是各个砝码的重量。相邻两个数之间必须严格用一个空格隔开。
注意：输入数据保证一定有解！如有多组解，输出任意一组即可！

 

样例输入

复制样例数据

67

样例输出

1 3 9 81
67 27

 

提示

小X给出的物品的质量为67pg，你可以在天平的左边放上4个砝码，重量依次为1,3,9,81总重量94ng，而右边放一个砝码质量为27ng，加上物体的重量67ng，恰好也是94ng，满足题目要求，此时天平的左右两端平衡。

对于20%的数据，W<=100
对于另外20%的数据，W<=10000，最多只用到5个砝码
对于另外20%的数据，W<=1000000，所有砝码都放在左边
对于另外20%的数据，W<=1000000
对于100%的数据，W<=1015。

题解：我们看到所有的数都是3的幂次

所以我们可以想到 如果一个数的三进制 都是1或0那么这个数绝对可以被三进制表示出

比如

27  1000  40 1111 可以表示出来

之后会有几种情况 

67  2111 这时候我们考虑怎么把67+3的幂表示为 三进制 全1的数

也就是 67+x=y。我们看到 67的第四位 为2 我们给他加一个 27 这时候变成 10111 =67+27

就有了 样例的输出

67+27=94  94是全是1或0的，并且27这个权值上是0 所以这样就能分解出来了

如果49 1211 这种 我们加上一个 9 变成 2011 这时候还需要加一个 27 变成 10011

所以 49+9+27=81+1+3

AC：

#include <bits/stdc++.h>
#include <hash_map>
#include <string>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll save[105];
ll L[105],R[105];
ll cnt=0;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        b/=2;a=a*a;
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    ll temp=n;
    while(temp)
    {
        save[++cnt]=temp%3;
        temp/=3;
    }
    int p1=0,p2=0;
    ll res=0;
    for(int i=1;i<=cnt+1;i++)
    {
        if(save[i]==2)
        {
            int k=i+1;
            while(1)
            {
                if(save[k]+1<3) {save[k]=save[k]+1;break;}
                save[k]=(save[k]+1)%3;
                k++;
            }
            R[++p2]=i;
        }
        else if(save[i]==1)
            L[++p1]=i;
    }
    sort(L+1,L+1+p1);
    sort(R+1,R+1+p2);
    for(int i=1;i<=p1;i++)
    {
        if(i==1) printf("%lld",qpow(3,L[i]-1));
        else printf(" %lld",qpow(3,L[i]-1));
    }
    printf("\n");
    printf("%lld",n);
    for(int i=1;i<=p2;i++)
        printf(" %lld",qpow(3,R[i]-1));
    return 0;
}