Comentário Noic OBI 2020 - Fase 1 Turno A - Programação Nível 1

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:


#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
}

view raw

Piloto.cpp

hosted with ❤ by GitHub

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:


#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");
}
}

view raw

fissura.cpp

hosted with ❤ by GitHub

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: