Comentário por Anita Ramos e Pedro Racchetti
Para conferir a prova na íntegra, clique aqui.
Piloto Automático
Conhecimento prévio necessário:
Esse é um problema bem simples, que pode ser resolvido apenas com comandos de condição, como $$if$$ e $$else$$. Assim, depois de declarar as variáveis e ler toda a entrada, utilizamos as fórmulas dadas pelo próprio enunciado para verificar o que deve ser feito com a velocidade. Assim:
- Se $$(B-A)<(C-B)$$, $$B$$ desacelera;
- Se $$(B-A)>(C-B)$$, $$B$$ acelera;
- Se $$(B-A)=(C-B)$$, $$B$$ mantém a velocidade.
Complexidade: $$O(1)$$.
Segue o código comentado para melhor compreensão da solução:
This file contains hidden or 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<bits/stdc++.h> //biblioteca utilizada | |
| using namespace std; | |
| int main() | |
| { | |
| int A,B,C; //declaração das variáveis | |
| scanf("%d", &A); //leitura da 1º linha de entrada | |
| scanf("%d", &B); //leitura da 2º linha de entrada | |
| scanf("%d", &C); //leitura da 3º linha de entrada | |
| if((B-A)<(C-B))printf("1"); //se a distancia entre 'A' e 'B' é menor que a distancia entre 'C' e 'B', imprimi 1 | |
| if((B-A)>(C-B))printf("-1"); //se a distancia entre 'A' e 'B' é maior que a distancia entre 'C' e 'B', imprimi -1 | |
| if((B-A)==(C-B))printf("0"); //se as distancias entre 'A' e 'B' e entre 'C' e 'B' forem iguais, imprimi 0 | |
| return 0; //retorna a 0 | |
| } |
Fissura Perigosa
Conhecimento prévio necessário:
Para resolver esse problema podemos usar uma DFS ou BFS (no código abaixo foi utilizada a DFS) para realizarmos um flood fill na matriz, partindo da posição do canto superior esquerdo. Além disso, precisamos garantir que, ao passar de uma posição a outra, essa nova posição não tem altitude maior que a força inicial. Outro possível caso de erros acontece quando a primeira posição tem altitude maior que a força, e o modo de entrada, já que a matriz é dada como uma série de $$strings$$ de números.
Complexidade: $$O(N^2)$$
Segue o código, comentado, para melhor compreensão:
This file contains hidden or 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<bits/stdc++.h> | |
| using namespace std; | |
| int orig[512][512]; //matriz original, dada na entrada. | |
| int dx[5] = {1, 0, -1, 0}; | |
| int dy[5] = {0, 1, 0, -1}; //vetores de auxílio, que servirão como | |
| //arestas no grafo. | |
| int n, f; | |
| void dfs(int i, int j){ | |
| orig[i][j] = 100; | |
| //definimos a posição i j como 100, valor absurdo | |
| //para que, no momento de saída, se reconheca o fato que é de fato uma | |
| //posição atingida pela lava | |
| for(int k = 0; k < 4; k++){ | |
| int ii = i + dx[k]; | |
| int jj = j + dy[k]; | |
| if(ii <= 0 || ii > n || jj <= 0 || j > n) continue; | |
| if(orig[ii][jj] > f) continue; | |
| dfs(ii, jj); | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d", &n, &f); | |
| for(int i = 1; i <= n; i++){ | |
| for(int j = 1; j <= n; j++){ | |
| char c; | |
| scanf(" %c", &c); | |
| //lemos cada posição como um caractér, e depois os transformamos | |
| //em um inteiro | |
| int k = c – '0'; | |
| orig[i][j] = k; | |
| } | |
| } | |
| if(orig[1][1] <= f){ | |
| dfs(1, 1); | |
| //se a posicao inicial tiver altitude menor que a forca, iniciamos a DFS | |
| } | |
| for(int i = 1; i <= n; i++){ | |
| for(int j = 1; j <= n; j++){ | |
| if(orig[i][j] > 9){ | |
| //todos os poontos atingidos estao marcados como 100 | |
| printf("*"); | |
| }else{ | |
| printf("%d",orig[i][j]); | |
| } | |
| } | |
| printf("\n"); | |
| } | |
| } |
Pandemia
Conhecimento prévio necessário:
Para esse problema, podemos primeiro perceber que qualquer reunião que tenha acontecido antes do primeiro amigo ser infectado, não influenciará na resposta, portanto podemos ignorá-las. Iremos guardar as reuniões em um vetor de $$vectors$$, onde cada $$vector$$ desse vetor guarda os amigos que estiveram presentes na reunião. Além disso, iremos usar um vetor de marcação para representar os amigos já infectados. Como o total de reuniões e amigos são pequenos, podemos fazer um algoritmo com complexidade $$O(N*M)$$. Podemos portanto passar por todas as reuniões, e sempre que houver ao menos uma pessoa infectada, marcamos todos os presentes no vetor de marcação. No final, basta iterar pelo vetor de marcação, e aumentar a resposta por um sempre que houver um infectado marcado.
Complexidade: $$O(N*M)$$
Segue o código, comentado para melhor compreensão: