WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM604 Div1 Easy "PowerOfThree"

問題

TopCoder Statistics - Problem Statement

キツネのシエルはロボットを持っていた。このロボットは無限に広がる平面に置かれている。はじめに座標(0, 0)からスタートする。ロボットは複数ステップ動くことができる。各ステップは0から番号が付けられている。

各ステップで、シエルは左(x座標が減少)、右(x座標が増加)、上(y座標が増加)、そして下(y座標が減少)の4方向の内いずれかを選択する。kステップ目では、ロボットは3^kだけ選択された方向に移動する。ステップは0, 1, 2, 3... と行わなければならず、どれもスキップすることはできない。

あなたはint x, yが与えられる。ロボットが任意のステップで座標(x, y)に到達することができるかどうかを返せ。

制約

-10^9 <= x, y <= 10^9


考えたこと

まずマイナスはプラスで考える(プラスでできるならマイナスでもできるから)
それからx及びyを3進数にして考えると、以下の3つの操作ができる事になる。

0 -> 1

0 0 0 0 0 0
   +1
0 0 1 0 0 0


0 -> 2(範囲)

0 0 0 0 0 0
 +1    -1
0 0 2 2 2 0


2 -> 1

0 0 2 2 2 0
     -1
0 0 2 1 2 0

ということで、以下のように考えることができるようだ。
☆0だったら
基本は何も引かない、何も足さない
だけど、前に2があったら+1しなければならない

☆1だったら
0を1にするにしろ、2を1にするにしろ、必ず足し引きしなければならない。

☆2だったら
下の桁から調べていって、始めに2が出てきたら-1しなければならない。
だけど、0を挟まずに、また2がでてきても足し引きはしない。

事後

これでEasyなの・・・

ソースコード

class PowerOfThree {

    public:

    string ableToGet(int x, int y) {

        if (x < 0) x = -x;
        if (y < 0) y = -y;

        bool xFlg = false;
        bool yFlg = false;
        while (x > 0 || y > 0 || xFlg || yFlg) {
            int x3 = x % 3;
            int y3 = y % 3;

            bool xUse = false;
            bool yUse = false;

            // 0
            if (x3 == 0){
                xUse = xFlg; xFlg = false;
            }
            if (y3 == 0){
                yUse = yFlg; yFlg = false;
            }

            // 1
            if (x3 == 1) xUse = true;
            if (y3 == 1) yUse = true;            

            // 2
            if (x3 == 2 && !xFlg) xUse = xFlg = true;
            if (y3 == 2 && !yFlg) yUse = yFlg = true;

            if (!(xUse ^ yUse)) return "Impossible";

            x /= 3;
            y /= 3;
        }

        return "Possible";
    }
};