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: