Solução Competição de Chocolate

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: