SRM604 Div1 PowerOfThree

問題概要

(0,0)からk回目には3^kずつ4方へ移動する.(x,y)に辿り着く方法はあるか.

解法

解説AC.
x,yを正と仮定する.
x,yを3進数で考えると,k回目の移動は[tex;k]桁目に対する操作と同じ.
各桁について,x,yがどちらも0のとき,その回はどちらも動かせないので"Impossible"
どちらも0でないとき,両方共動かすことはできないので"Impossible"
片方が1のとき,その桁を0にする(盤上においては近づく).
片方が2のとき,その桁を3(=10(3))にする(盤面においては遠ざかる).
どちらも値が0になったら"Possible"

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;

void debug(int x){
    while(x){
        cerr<<x%3;
        x/=3;
    }cerr<<endl;
}

class PowerOfThree{
public:
    string ableToGet(int x,int y){
    	x=abs(x);y=abs(y);
        while(1){
            debug(x);debug(y);
            if(!x&&!y){
                return "Possible";
            }
            if(x%3&&y%3){
                return "Impossible";
            }
            if(!(x%3)&&!(y%3)){
                return "Impossible";
            }
            if(x%3==1){
                x--;
            }else if(x%3==2){
                x++;
            }else if(y%3==1){
                y--;
            }else{
                y++;
            }
            x/=3;
            y/=3;
        }
    }
};