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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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. | |
| } |