Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2367
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2367
Competição de Chocolate
Por OBI - Olimpíada Brasileira de Informática 2009 
Brazil
Timelimit: 1
Carlos e Paula acabaram de ganhar um saco com bolinhas de chocolate. Como sabem que vão comer tudo muito rápido inventaram uma brincadeira:
- Eles vão comer de forma alternada, um depois o outro, sendo que sempre a Paula começa.
- A cada vez, só se pode comer de 1 a M bolinhas, sendo o M decidido pela mãe de Paula, de forma que não engasguem com o chocolate.
- Se um comeu K bolinhas em sua vez, o próximo não pode comer o mesmo tanto, tendo que comer um número de bolinhas distinto.
- Quem não puder mais jogar de maneira válida perde.
Um exemplo de partida para M = 5 e 20 bolinhas, onde Carlos ganhou:
Observe que no final Carlos não poderia comer 2 bolinhas para ganhar, pois seria o mesmo que Paula comeu na vez anterior. Mas Paula também não pôde comer a última bolinha, pois Carlos havia comido apenas uma na rodada anterior, assim Paula ficou sem opção de jogada e perdeu.
Ambos são muito espertos e jogam de maneira ótima, de forma que se existe para um deles uma sequência de jogadas que garante a vitória independente da jogada do outro, essa pessoa jogará dessa forma.
Sua tarefa é determinar quem vai ganhar a brincadeira, se ambos jogam de forma ótima.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).
A entrada consiste de uma linha contendo dois inteiros N (2 ≤ N ≤ 106) e M (2 ≤ M ≤ 103), sendo N o número de bolinhas de chocolate e M o número de bolinhas permitidas por vez.
Saída
Seu programa deve imprimir, na saída padrão, uma linha, contendo o nome do vencedor, como exemplificado abaixo.
| Exemplos de Entrada | Exemplos de Saída |
|
5 3 |
Paula |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 1001010
int dp[MAXN], proibido[MAXN], n, m;
int solve() {
for (int i = 0; i < = n; i++) {
if (dp[i] == 0) {
for (int j = 1; j < = m; j++) {
dp[i + j]++;
proibido[i + j] = j;
}
} else if (dp[i] == 1) {
dp[i + proibido[i]]++;
proibido[i + proibido[i]] = proibido[i];
}
}
return dp[n];
}
int main() {
scanf("%d %d", &n, &m);
if (solve())
printf("Paula\n");
else
printf("Carlos\n");
return 0;
}
Input
Output