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; } };