Solução Informática - Nível Iniciante - Semana 10

Solução por Pedro Racchetti

Conteúdos usados:

Loops

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.
	}

view raw

imitater.cpp

hosted with ❤ by GitHub