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

土下座しながら探索中

主に競技プログラミング

TCO17 Algorithm Round 2A Easy FoxAndCake2

以下備忘録

解法 :
与えられる整数c,sの偶奇で場合分けする。
1. cとsがともに偶数ならば Possible ( 分割しなくても gcd(c,s) != 1 なので
2. cとsがともに奇数ならば
- c と s がともに 3 以上なら Possible ( (3,3) (c-3,s-3)とすればよい
- そうでないなら、 c か s の一方は1なので Impossible
3. cとsのうち片方だけが偶数ならば
- これを (偶、偶)(偶、奇)に分割する
  奇はできるだけ小さくしたほうがよいので 3
偶も(3とのgcdが1でないようなもののなかで)できるだけ小さくしたほうがよいので 6
  cとsから(3,6)のペアを作ったあとにc,sがそれぞれ2以上なら Possible
それ以外は Impossible

コード :

const string YES = "Possible";
const string NO  = "Impossible";

class FoxAndCake2 {
public:
  string isPossible( int _c, int _s ) {
    ll c = _c, s = _s;
    if( __gcd(c,s) != 1LL ) return YES;
    if( c % 2 == 1 && s % 2 == 1 && min(c,s) >= 3 )  return YES;
    ll even = c ,odd = s;
    if( !( even % 2LL == 0 ) ) swap(even,odd);
    odd -= 3LL;
    even -= 6LL;
    if( odd >= 2LL && even >= 2LL ) return YES;
    return NO;
  }
};