Solução por Lucca Siaudzionis
Imagine que é sua vez de jogar agora, onde a pilha está com $$X$$ chocolates, e você pode tirar qualquer quantidade de pedras de $$1$$ a $$X-1$$. Vamos chamar de $$count[X]$$ o número de jogadas ótimas que se podem fazer a partir de $$X$$ (i.e. o número de jogadas possíveis que você possa fazer tal que você obrigatoriamente vai vencer se continuar jogando de maneira inteligente). Note que, se $$count[X]$$ for maior que $$1$$, você sempre vai poder vencer o jogo a partir daquela posição, pois, independente do valor que é proibido de ser retirado, você ainda tem outro valor disponível que lhe garante a vitória.
Note então que se $$count[X] \ = \ 0$$, quem receber uma pilha com $$X$$ chocolates irá obrigatoriamente perder. Podemos então acrescentar $$1$$ a $$count[X+1]$$, $$count[X+2]$$, …, $$count[X+M-1]$$ e $$count[X+M]$$, pois quem começa com uma pilha com esses valores pode mandar para o adversário uma pilha com $$X$$ chocolates.
Há, também, o caso que $$count[X] \ = 1$$, nesse caso, só há uma maneira de ganhar começando com uma pilha com $$X$$ chocolates. Iremos então definir um outro valor $$forbid[X]$$ que será definido para todo $$X$$, mas que só terá utilidade para este caso. Neste caso, $$forbid[X]$$ será o valor que se tem que retirar, tendo uma pilha com $$X$$ chocolates, para garantir a vitória. Com isso, caso uma pessoa receba uma pilha com $$X \ + \ forbid[X]$$ chocolates, ela consegue ganhar se decidir retirar $$forbid[X]$$ chocolates da pilha, ou seja, acrescentamos $$1$$ a $$count[X \ + \ forbid[X]]$$.
Calculando $$count[i]$$ para todo $$i$$ em que $$1 \leq i \leq N$$, teremos que Paula irá ganhar se, e somente se, $$count[N] \geq 1$$ (pois Paula pode retirar qualquer valor menor que $$N$$ da pilha).
O código então fica:
https://gist.github.com/luccasiau/ce020542fa75db4d1f0f
Deixe um comentário