Solução Competição de Chocolate (PJ)

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Vamos pensar na estratégia vencedora do jogo. Se for múltiplo de m+1 o segundo jogador vai ganhar, pois note que não importa quantos chocolates o primeiro jogador tirar (de 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 é 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ão for múltiplo de m+1? Então o primeiro jogador irá ganhar de maneira semelhante. Seja r o resto que 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 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 m, e que imprima uma única linha com "Carlos", se for múltiplo de m+1, ou "Paula", caso contrário. Segue o código para melhor entendimento:

O problema lhe parece fácil? Clique aqui para ver uma versão bem mais desafiadora dele, com solução aqui.

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