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"; } };