Solução por Rogério Júnior
Vamos pensar na estratégia vencedora do jogo. Se n for múltiplo de m+1 o segundo jogador vai ganhar, pois note que não importa quantos chocolates o primeiro jogador tirar (de 1 a m), o segundo jogador sempre vai poder completar, tirando os que faltam para que sejam retirados m+1 chocolates. Assim, a cada duas rodadas, serão retirados m+1 chocolates e, como n é múltiplo de m+1, ficaremos sem chocolates em uma das jogadas do segundo jogador, que ganhará. Nesse caso, o ganhador é Carlos.
Se você não entendeu, pense na seguinte simulação: imagine que são 12 chocolates e podemos comer até 3 deles a cada jogada. Note que 12 é múltiplo de 3+1 (4), logo basta a Carlos que sempre complete o que falta para esse valor. Imagine que na primeira jogada Paula tira uma quantidade arbitrária de bolinha, digamos 2. Carlos irá completar o que falta para que saiam 4, tirando também 2. Agora temos 8 chocolates e Paula irá tirar 3, por exemplo. Carlos novamente completa o que falta para 4, tirando um chocolate. Agora só temos 4 chocolates e qualquer quantidade que Paula tirar dará a vitória a Carlos, que irá tirar o que sobrar. Imagine que ela tira exatamente 1. Agora Carlos completa, novamente, o que falta para 4, tirando os 3 chocolates que ainda restam e ganhando, portanto, o jogo.
Mas e se n não for múltiplo de m+1? Então o primeiro jogador irá ganhar de maneira semelhante. Seja r o resto que n deixa na divisão por m+1. Basta ao primeiro jogador que, na primeira jogada do jogo, tire exatamente r chocolates. Paula sempre poderá fazer essa jogada porque sabemos que o resto em uma divisão é menor que o divisor, ou seja r < m+1. Feito isso, o número de chocolates que vai restar é múltiplo de m+1, mas agora é a vez do segundo jogador! Assim como no caso anterior, não importa quantos chocolates Carlos tirar, Paula sempre será capaz de completar o que falta para que sejam retirados m+1 chocolates a cada duas rodadas, ganhando ela, portanto, o jogo.
Assim, resolvemos o problema em O(1), apenas pensando um pouco com combinatória. Basta fazer um programa que lê os valores dos dois inteiros n e m, e que imprima uma única linha com "Carlos", se n for múltiplo de m+1, ou "Paula", caso contrário. Segue o código para melhor entendimento:
This file contains 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
| #include <cstdio> | |
| int n, m; | |
| int main(){ | |
| // leio os valores de n e m | |
| scanf("%d %d", &n, &m); | |
| // se n for múltiplo de m+1, Carlos ganha | |
| if(n%(m+1)==0) printf("Carlos\n"); | |
| // Caso contrário, Paula ganha | |
| else printf("Paula\n"); | |
| return 0; | |
| } |
O problema lhe parece fácil? Clique aqui para ver uma versão bem mais desafiadora dele, com solução aqui.