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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // competicao_de_chocolate.cpp | |
| // programas2 | |
| // | |
| // Created by Lucca Siaudzionis on 29/04/14. | |
| // Copyright (c) 2014 Luccasiau. All rights reserved. | |
| // | |
| #include <cstdio> | |
| #define MAXN 1001010 | |
| int n, m; | |
| int count[MAXN]; | |
| int forbid[MAXN]; | |
| int solve(){ | |
| /* | |
| Forbid[i] é o número de chocolates que eu tenho que tirar em i para vencer o jogo | |
| se forbid[i] for proibido, a posição i perde uma maneira de ganhar | |
| Count[i] é o número de maneiras que eu tenho de ganhar o jogo a partir da posição i | |
| se count[i] >= 2, a posição é estritamente vencedora (eu tenho duas jogadas possíveis que me fazem ganhar e ao máximo uma foi proibida) | |
| se count[i] = 1, a posição é perdedora <=> foi-se retirado forbid[i] na jogada anterior => count[i + forbid[i]]++ | |
| se count[i] = 0, a posição é estritamente perdedora | |
| Note que precisamos apenas que count[n] >= 1 para que Paula ganhe, pois é a primeira jogada a ser feita | |
| */ | |
| for(int i = 0;i <= n;i++) count[i] = forbid[i] = 0; | |
| for(int i = 0;i <= n;i++){ | |
| if(!count[i]){ //se a posição for perdedora (note que eu começo com i = 0) | |
| for(int j = 1;j <= m;j++){ //faço todas as posições seguintes aumentarem seu valor de Count | |
| count[i+j]++; | |
| forbid[i+j] = j; //colocando um valor de forbid nelas (nao fará diferença se count[i+j] >= 2) | |
| } | |
| } | |
| else if(count[i] == 1 && i + forbid[i] <= n){ //se eu só tenho uma maneira de ganhar a partir de i, eu posso transformá-la numa posição perdedora | |
| count[i + forbid[i]]++; //bloqueando forbid[i], a posição i passa a ser perdedora | |
| forbid[i+ forbid[i]] = forbid[i]; | |
| } | |
| } | |
| return count[n]; //se se tem alguma maneira de ganhar a partir de N, Paula ganha | |
| } | |
| int main(){ | |
| scanf("%d %d",&n,&m); | |
| printf("%s\n", solve() ? "Paula" : "Carlos"); | |
| return 0; | |
| } |
Comente