Por: Rodrigo Burgos Dominguez

Apenas paso la final de ciudades Mexicanas, revisando los problema me encontré con este problema en particular A Game with Candies , lo primero que se me ocurrió fue la teoría de los Grundy Numbers, pero no salía con XOR, después de un rato de pensar me di cuenta que para que el primer jugador ganara tendría siempre que dejar al siguiente jugador con un numero par de números mayores, asi cuando el tirará siempre fuera impar y tuviera la forma de llavarlo a par, con esta idea surgen los siguientes casos:

Primero si el numero de elementos mayores es par o bien todos son ceros, el primero jugador pierde ya que siempre va a volver impar el numero de elementos mayores. En otro caso Gana.

// en el arreglo mx el elemento 0 es el mayor de los números dados
// el mx[1] es el segundo mayor, y el arreglo count[ valor ] contiene
// el numero de veces que se ingreso el numero ‘valor’</pre>
if( count[ mx[0] ] % 2 == 0 || mx[0] == 0){
    printf("0\n");
    continue;
}

Si el numero de elementos con valor mayor es mas de uno , entonces la respuesta el numero de elemento mayores count[mx[0]] por el elemento mayor ( ya que podemos poner 0, 1, …, mx[0] -1 ) y volvemos par el numero de elementos mayores.

 if( count[mx[0]] > 1 ){
   printf("%lld\n", (long long)(count[mx[0]]) * (long long)( mx[0]));
 }

Que pasa en el caso que mx[0] es igual a 0 ( si el elemento mas grande que se dio es igual a 0 ), esto indica que ya todos están en 0, por lo tanto el primero jugador piede.

if( mx[1] == 0){
  printf("1\n");
}

En otro caso, máximo valor es único y no es cero, por tanto al que ver los dos casos cuando el segundo valor mas grande es par o impar:
Cuando es par , podemos volver al elemento mayor 0 , 1, … mx[1] – 1 , y cuando es impar solamente podemos colocarlo de una manera , igual al segundo mas grande, para forzarlo a ser par.

else if( count[ mx[1] ] % 2 == 0 ){
   printf("%d\n", mx[ 1 ] );
}else{
  printf("%d\n", 1);
}

Les dejo el código:

/*

Autor: Rodrigo Burgos Dominguez.

*/
# include <stdio.h>
# include <string.h>

int count[1000001];

main(){
  int ncases, cases, mx[3], x, y, n, value;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ) {
   scanf("%d", &n);
   memset( count, 0, sizeof( count ));
   memset( mx, 0, sizeof( mx ));
   for( x = 0; x < n; x++){
     scanf("%d", &value);
     count[ value ]++;
     for(y = 0; y < 2; y++) if( value > mx[ y ]){
       mx[ y + 1 ] = mx[ y ];
       mx[ y ] = value;
       break;
     } else if( value == mx[ y ]) break;
   }
   if( count[ mx[0] ] % 2 == 0 || mx[0] == 0){
     printf("0\n");
     continue;
   }
   if( count[mx[0]] > 1 ){
     printf("%lld\n", (long long)(count[mx[0]]) * (long long)( mx[0]));
   }else{
     if( mx[1] == 0){
      printf("1\n");
     } else if( count[ mx[1] ] % 2 == 0 ){
      printf("%d\n", mx[ 1 ] );
     }else{
       printf("%d\n", 1);
     }
   }
 }
return 0;
}