Solução por Pedro Racchetti
Conteúdos usados:
Primeiro, chamaremos o total de cartas na mesa de $$total$$ e o menor número de cartas em uma pilha de $$minimo$$. Além disso, perceba que $$0$$ é par, e portanto, o jogador que sempre conseguir entregar movimentos com $$total$$ par ganha.
Podemos dividir o problema em 2 casos: onde $$N$$ é par, e onde $$N$$ é ímpar.
Se $$N$$ for ímpar, podemos ver que cada movimento irá inverter a paridade de $$total$$, já que ao se-remover $$1$$ carta, a paridade sempre vai inverter, e ao se-remover um número ímpar de cartas, a paridade de $$total$$ também irá inverter. Portanto, pela regra de entregas já mencionadas com $$N$$ ímpar: se $$total$$ é ímpar, Lowie ganha, caso contrário Imitater ganha.
Se $$N$$ for par, teremos que dividir o problema em mais 4 casos:
Se $$total$$ e $$minimo$$ forem par, Imitater, ou o jogador que receber esse estado, ganha. Como $$total$$ é par, o número de pilhas com número ímpar de cartas é par, chame esse número de $$P$$. Os movimentos que Lowie pode fazer são:
- Tirar uma carta de uma das $$P$$ pilhas com número de cartas ímpares, Imitater pode tirar uma carta de uma das$$P – 1$$ pilhas restantes, voltando ao estado de antes, agora com $$P$$ sendo exatamente 2 pilhas menor.
- Tirar uma carta de qualquer outra pilha. Nesse caso, como a pilha tirada tinha um número par de cartas Imitater pode imitar o movimento, voltando para o caso inicial, com que $$total$$ e $$P$$ continuem par.
- Se Lowie tirar uma carta de todas as pilhas, Imitater pode imitar o movimento, voltando ao estado de antes, com $$total$$ par.
Logo, independente do que $$Lowie$$ fizer, Imitater consegue entregar $$total$$ mantendo sua paridade, e como $$total$$ é par, Imitater, ou seja quem receber esse caso, perde.
Se $$total$$ for par e $$minimo$$ for ímpar: Lowie pode tirar uma carta de todas as pilhas. Como $$N$$ é par, $$total$$ continua par, mas $$minimo$$ vira par, ou seja Lowie estaria entregando o caso acima, ganhando o jogo.
Se $$total$$ é ímpar mas $$minimo$$ é par, Lowie pode tirar uma carta de qualquer pilha que não contenha $$minimo$$ cartas, transformando $$total$$ em par, entregando o primeiro desses casos, ganhando o jogo.
Se $$total$$ e $$minimo$$ são ímpares, Lowie pode tirar uma carta de qualquer pilha com $$minimo$$, fazendo com que $$total$$ e $$minimo$$ virem pares, entregando o primeiro caso, e ganhando o jogo.
Se juntarmos ambos, podemos ver que se $$total$$ é ímpar, Lowie sempre ganha. Se $$total$$ é par, temos que:
- Se $$N$$ for ímpar, Imitater ganha.
- Se $$N$$ for par e $$minimo$$ for par, Imitater ganha.
- Em qualquer outro caso, Lowie ganha.
Segue o código, comentado para melhor compreensão da solução:
| #include<bits/stdc++.h> | |
| using namespace std; | |
| int n, minimo, total; //váriaveis usadas | |
| int main(){ | |
| minimo = 1500; // inicializamos minimo com um valor maior que qualquer pilha. | |
| scanf("%d", &n); //lêmos o número de pilha | |
| for(int i = 0; i < n; i++){ | |
| int x; | |
| scanf("%d", &x); | |
| total += x; | |
| minimo = min(x, minimo); | |
| //lemos os valores das pilhas. | |
| } | |
| if(total%2 == 1) printf("lowie\n"); // se total for ímpar, lowie ganha | |
| else if(n%2 == 1) printf("imitater\n"); // se total nao for ímpar, é par. Se total é par, e n é impar, imitater ganha | |
| else if(n%2 == 0 && minimo%2 == 0) printf("imitater\n"); // se total for par, n for par e minimo for par, imitater ganha | |
| else printf("lowie\n"); // em qualquer outro caso lowie ganha. | |
| } |
