uva 1500 - Alice and Bob(推理)

uva 1500 - Alice and Bob(推理)

題目連接：uva 1500 - Alice and Bob

題目大意：在黑板上又一個序列，每次操作可以選擇一個數減1，或者是合並兩個數，一個數被減至1則自動消除，不能操作者輸。

解題思路：結論，對於大於1的數可以看成是一個整數s，為消除他們的總操作步數,包括減1以及合並，c為列中1的個數，如果s>2的話，c或者是s為奇數則為必勝，否則必敗。若s≤2的話（s=2或者s=0）是，判斷c是否為3的倍數，是的話必敗，不是的話必勝。
證明：s>2時，s和c均為偶數是為必敗態。
s為奇數，c為偶數：先手操作，將s減1，轉移至必敗態。 s為偶數，c為奇數：先手操作，將一個1減1，則c會減少1，轉移至必敗態。
s為奇數，c為奇數：將一個1和s中的一個數合並。轉移至必敗態。
s為偶數，c為偶數：s減1，則s為奇數c為偶數，必勝態；c減1，則s為偶數c為奇數，必勝態；合並1和非1數，s奇數c奇數，必勝態；
s==0或者s==2時，當c%3==0時，為必敗態。
c%3==1時，將一個1減1，c%3==0，轉移至必敗態。
c%3==2時，對於s==0，合並兩個1，則變為s+2，c-2，此時如果s==0，則變為s==2時，c%3==0的必敗態；對於s==2，將s減1，則變為s變為1，於是1的個數又增加1，所以c%3==0，必敗態。
c%3==0時，減掉一個1即為必勝態。

/******************
 * c為1的個數，s為其他非1的總步數，包括合並。
 * s > 2時，c若為奇數則必勝，為偶數則s為奇數時必勝；
 * s == 2 || s == 0時，c不為3的倍數時必勝
******************/
#include 
#include 
#include 

using namespace std;

int n, c, s, x;

void init () {
    c = s = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x == 1)
            c++;
        else if (x > 1)
            s += (x + 1);
    }

    if (s)
        s--;
}

bool judge () {
    if (s > 2)
        return (c&1) || (s&1);
    if (s == 0)
        return c % 3;
    return c % 3;
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int k = 1; k <= cas; k++) {
        init();
        printf("Case #%d: %s\n", k, judge() ? "Alice" : "Bob");
    }
    return 0;
}