読者です 読者をやめる 読者になる 読者になる

SRM 604 Div2 Medium PowerOfThreeEasy

問題

SRM 604 - TopCoder Wiki

2次元平面上の(0, 0)地点にいる. 各kステップにおいて(0ステップから始まる) y軸方向x軸方向のどちらかに3k移動する.

(x, y)が与えられた時,到達可能かどうかを判定する問題

解答

全探索.

各ステップで必ずx, yのどちらかの方向に移動しなくてはいけないので,考慮すべき場合の数はそれほど多くない. 入力から考えると最大で20ステップ程度なので220ぐらい. また,移動方法が特殊なので枝刈りはかなり効く.

class PowerOfThreeEasy
{
public:
  bool calc(int x, int y, int cost){
      if (x == 0 && y == 0) return true;
      bool res = false;
      if (x >= cost) res |= calc(x-cost, y, cost*3);
      if (y >= cost) res |= calc(x, y-cost, cost*3);
      return res;
    
  }
  string ableToGet(int x, int y)
    {
      return calc(x, y, 1)?"Possible" : "Impossible";
    }
};