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

SRM 620 Div2 Medium PairGameEasy

問題

SRM 620 - TopCoder Wiki

二つの数のペア(x,y)が与えられた時,このペアから(x+y, y)もしくは(x, x+y)に変換できる. このとき,(a, b), (c, d)が与えられた時,(a, b)を上記の操作を繰り返して(c, d)に変換できるかを判定する問題.

解答

やるだけ. ただしメモ化はする.

追記

メモ化したつもりが出来ていなかった・・・ なのにシステムテストを通っているのはなぜだw

class PairGameEasy
{
public:
  vector<vector<int> > memo;
  bool calc(int a, int b, int c, int d){
    if (a > c || b > d) return false;
    if (memo[a][b] != 0) return memo[a][b] == 1;
    if (a == c && b == d) {
      memo[a][b] = 1;
      return true;
    }
    return calc(a + b, b, c, d) || calc(a, a + b, c, d);
  }
  string able(int a, int b, int c, int d)
    {
      if (!(a <= c && b <= d)) return "Not able to generate";
      memo = vector<vector<int> >(c+1, vector<int>(d+1, 0));
      return calc(a, b, c, d) ? "Able to generate" : "Not able to generate";
    }
};