Solução Pulo do Sapo

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Se o sapo começa na pedra P, e pula sempre uma distância D, então ele pode alcançar qualquer pedra X tal que o resto da divisão de X por D seja P ou congruente a ele (X \equiv P\mod \ D). Deste modo, para cada sala, marcaremos todas as pedras com essa congruência módulo D. Para isso, começaremos da primeira pedra que satisfaça a condição, a marcaremos, e pularemos D pedras para marcar a segundo, outras D para marcar a terceira e assim, de D em D pedras, marcaremos todas as pedras que tal sapo pode alcançar. Tais pedras serão marcadas no vetor booleano marcado. Segue o código para maior entendimento:

Nosso leitor Roger Benet também apresentou uma solução correta. Nela, ele cria uma função que recebe a pedra em que o sapo está e quantas pedras ele pode pular. Com isso, ele simula todos os possíveis pulos do sapo, para frente e para trás, e marca em um vetor todas as pedras que ele alcança. Feito isso, ele apenas imprime os estado de cada pedra: alcançada ou não.

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