Analysis Problem C - Playing with Stones

NIM game has become so popular in programming contests recently thanks to TopCoder's Algorithm Games tutorial. To my surprise, this is the first problem solved in the contest (in 12 minutes)! This could mislead other teams to think that this problem is that easy. Well, it becomes easy only when you already learn about Grundy Numbers beforehand. I recommend you to read the TopCoder's tutorial above if you do not know about NIM game or Grundy Numbers.

So, this problem is obviously a variant of a NIM game. What we have to do is to map this problem into an equivalent NIM game via Grundy Numbers. For certain game state in this problem, it is equivalent to a certain Grundy Number. You will need to sketch how the Grundy number is formed in this problem. After you've figured it out, the solution is just to xor all the Grundy numbers just like a NIM game.

#include <stdio.h>

long long Grundy(long long x){
    return x%2==0 ? x/2 : Grundy(x/2);
}

int main(){
    long long T,N,res,A;
    scanf("%lld",&T);
    while (T--){
        scanf("%lld",&N);
        for (int i=res=0; i<N; i++){
            scanf("%lld",&A);
            res ^= Grundy(A);
        }
        puts(res?"YES":"NO");
    }
}