SRM604 div2 med PowerOfThreeEasy

問題概要

• step k でx方向かy方向に3^k進む
• stepは0から始まる
• xとyが与えられるのでその座標にちょうど到達できるか判定せよ

制約

• 0≦x≦10⁹
• 0≦y≦10⁹

解説

3¹⁹ = 1162261467なので高々19ステップで制約の座標には到達できるかどうかわかる。

各stepでx方向に行くかy方向に行くか全探索O(2¹⁹)。

コード

class PowerOfThreeEasy {
public:
  string ableToGet(int x, int y) {
    int th[20]; FOR(i,0,20) th[i] = pow(3,i);
    FOR(i,0,1<<20) {
      int X = 0, Y = 0;
      FOR(j,0,20) {
        if(X == x && Y == y) return "Possible";
        if((i>>j)&1) X += th[j];
        else Y += th[j];
      }
      if(X == x && Y == y) return "Possible";
    }
    return "Impossible";
  }
};