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 (
). 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:
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> | |
| #define MAXN 110 | |
| bool marcado[MAXN]; | |
| int n, m; | |
| int main(){ | |
| scanf("%d %d", &n, &m); // leio os valores de n e m | |
| for(int i=1; i<=m; i++){ // para cada sapo | |
| // declaro e leio seus valores de P e D | |
| int p, d; | |
| scanf("%d %d", &p, &d); | |
| // e marco as pedras que ele pode alcançar | |
| for(int i=p%d; i<=n; i+=d) | |
| marcado[i]=true; | |
| } | |
| // depois imprimo os estado de cada pedra | |
| for(int i=1; i<=n; i++) printf("%d\n", marcado[i]); | |
| return 0; | |
| } |
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.
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 pedras[110]; | |
| int n,m; | |
| void busca (int ini,int fim,int d){ | |
| if(fim == n){ | |
| while(ini <= fim){ | |
| pedras[ini] = 1; | |
| ini += d; | |
| } | |
| } | |
| if(fim == 1) { | |
| while(ini >= fim){ | |
| pedras[ini] = 1; | |
| ini -= d; | |
| } | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d", &n, &m); | |
| while(m-- > 0){ | |
| int p,dis; | |
| scanf("%d %d", &p, &dis); | |
| busca(p,n,dis); | |
| busca(p,1,dis); | |
| } | |
| for(int i = 1; i <= n; i++) | |
| printf("%d\n",pedras[i]); | |
| } |