wustoj1284 Gold Medal

Problem Description

Input

Output

Sample Input

4 14
2 14
2 3

Sample Output

LEFT:1 3 9
RIGHT:27

No way!

LEFT:
RIGHT:3

想到三进制就变得无比简单的题

要注意 开始判断下w换成三进制长度是否>n 是的话肯定就no way了

cnt==n时 如果最后一位数刚好进位了 那么就进到n+1位上去了 也不行 

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;

ll pow3[25],le[30],ri[30];

int main()
{
    int tmp,n,w,go[35],cnt,i,rn,ln;
    pow3[0]=1;
    for(i=1;i<=20;i++)
        pow3[i]=pow3[i-1]*3;
    while(~scanf("%d%d",&n,&w))
    {
        memset(go,0,sizeof go);
        tmp=w;
        cnt=0;
        while(tmp>0)
        {
            go[cnt++]=tmp%3;
            tmp/=3;
        }
        if(cnt>n)
        {
            printf("No way!\n\n");
            continue;
        }
        ln=0;rn=0;
        for(i=0;i<cnt;i++)
        {
            if(go[i]==3)
            {
                go[i+1]++;
                go[i]=0;
            }
            if(go[i]==2)
            {
                le[ln++]=pow3[i];
                go[i+1]++;
            }
            else if(go[i]==1)
            {
                ri[rn++]=pow3[i];
            }
        }
        if(go[cnt])
        {
            if(cnt>=n)
            {
                printf("No way!\n\n");
                continue;
            }
            ri[rn++]=pow3[i];
        }
        printf("LEFT:");
        for(i=0;i<ln;i++)
        {
            if(i!=0) putchar(‘ ‘);
            printf("%lld",le[i]);
        }
        putchar(‘\n‘);
        printf("RIGHT:");
        for(i=0;i<rn;i++)
        {
            if(i!=0) putchar(‘ ‘);
            printf("%lld",ri[i]);
        }
        putchar(‘\n‘);
        putchar(‘\n‘);
    }
    return 0;
}

wustoj1284 Gold Medal,布布扣,bubuko.com

wustoj1284 Gold Medal

原文：http://blog.csdn.net/u011032846/article/details/22541141