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:
https://gist.github.com/PedroRacchetti/6332dd4f78d29b61141fd4a4b1572022