SnackDown 2016 - VCake

問題

縦と横が長さR,Cの長方形があり、それをいくつかの条件に基づいて切断し、指定された3つの面積(M,J,K)になるように分けろ、という問題です。
切断の条件は3つで、

• 長方形の辺と平行に切断する

• 一度切れ込みを入れたら、その部分は端から端まで切断する

• 切った後に二つに分かれる部分は、どちらも整数になるように切断する
  というものです。
  これをT回繰り返します。

解法

この問題はあたりまで計算量を落とさないといけないので、考察で殴る必要があります。
ということで考察をすると、まず一回目に例えば横と平行に切断するとしたとき、
ケーキはまず上下に分かれます。
3つに分けるには、上下に分かれたうちどちらかをもう一度切断する必要があります。が、残った片方はもう切断することはありません。
ということで、残る方を上側とすると、それは与えられた3つの大きさのうちのどれかにすでになっていなければなりません。
上側の面積が例えばMに一致するように切るとき、横の長さは一定なので、縦の長さは一意に決まってしまいます(MがCで割り切れなかったとき、条件をみたす切り方は存在しません)。
このように切断したとき、のこる下側の、縦の長さはR-M/Cとなります。
次は、残ったケーキを縦、または横に切断して、それぞれ面積がJ,およびKとなるかどうかを判定します。これも同様に調べることができます。
例えば再び横と平行に切断するとしたとき、
J、K両方がCで割り切れて、かつJ/CとK/Cの和がR-M/Cになれば、条件を満たす切断方法が存在します。
これを、必要な回数調べればよいです。
具体的には、RとCは交換可能なので2通り、最初に切り分けられた時点で決まるもの(先ほどの例でいうMです）を3つのうち1つ選ばなければならないので3とおり、最後に二回目の切断を縦できるか横できるかの2通りです。
全部で12通りほど調べて、それでも条件を満たす切断方法が存在しなければNo,すればYesになります。

以下が提出コードになります。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void prians(bool answer) {
  if(answer)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
ll t, r, c, mjk[3];

bool binary(ll x, ll y, ll z);

int main() {
  int i, k;
  bool ans = 0;
  cin >> t;
  while(t) {
    ans = 0;
    cin >> r >> c >> mjk[0] >> mjk[1] >> mjk[2];
    for(k = 0; k < 2; ++k) {
      for(i = 0; i < 3; ++i) {
        ans = binary(mjk[i], mjk[(i + 1) % 3],
                     mjk[(i + 2) % 3]);
        if(ans) break;
      }
      if(ans) break;
      swap(r, c);
    }
    prians(ans);
    --t;
  }
  return 0;
}

bool binary(ll x, ll y, ll z) {
  if(x % c != 0) return 0;
  ll now = r - x / c;
  if(now == 0) return 0;
  if(y % now == 0 && z % now == 0 &&
     (y / now + z / now) == c)
    return 1;
  if(y % c == 0 && z % c == 0 && (y / c + z / c) == now)
    return 1;
  return 0;
}