Solução Competição de Chocolate

0 Flares Facebook 0 0 Flares ×

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 1count[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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: