ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 620 Div2 Medium : PairGameEasy

解法・感想など


(a, b)という状態から(a+b, b)または(a, b+a)と遷移させていくときに(c, d)にできるかどうか判定する問題。

(c, d)から(a, b)に状態を戻すことを考える。
a > bのときは(a, b) -> (a - b, b)となり、
a < bのときは(a, b) -> (a, b - a)となる。

ソースコード

class PairGameEasy {
public:

  string able(int a, int b, int c, int d) {
    bool ok = false;
    
    while(true) {
      if(a == c && b == d) {
        ok = true;
        break;
      }
      if(c == d) break;
      if(c < 0 || d < 0) break;
      else if(c > d) c -= d;
      else d -= c;
    }
    
    return ok ? "Able to generate" : "Not able to generate";
  }
};