URAL 1051. Simple Game on a Grid

//By momo
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    if(n == 1) printf("%d\n", (m+1)/2);
    else if(n%3 == 0 || m%3 == 0) puts("2");
    else puts("1");
}

先排除 n 或 m 是 1 的可能。（數量很簡單算，就是 (n+1)/2）

---------------------------------------------------------------------------------

所以來討論只看 n > 1 且 m > 1 的情況：

證 n == 3k || m == 3k' 時，答案不可能是1:

作法（來自Yuhc's Blog）－

讓 a = (x+y)=0(mod 3), b = (x+y)=1(mod 3), c = (x+y)=2(mod 3),

當吃掉旁邊時，兩個減一，一個加一，且發現此情況，a = b = c, 故a%2 = b%2 = c%2,

因此場面剩下一個，代表其一為 1, 剩餘為 0, 不可能發生，QED。


再加上兩種神奇的消去法，可以把所有大的型態全部歸納出幾種，

除了其一是 3k 時是 2，其他都是 1。

方法一

方法二