Comentário Noic OBI 2019 - Fase 3 - Programação Nível Júnior

Comentário por Anita Almeida

Para conferir a prova na íntegra, clique aqui.

Pares de Números

Conhecimento prévio necessário:

Utilizamos as três variáveis $N, I$ e $F$ para ler a entrada, $R$ para ser o resultado final (saída), $S$ como a soma de um par de números, $n1$ como o primeiro número de um par de números escolhidos, $n2$ o segundo número desse mesmo par de números escolhidos e $MAXN$ como o tamanho do vetor $V[]$ .

Para comparar todos os pares que podem ser formados com a sequência de números de entrada utilizamos dois loops a partir do comando $for()$ e uma estrutura condicional a partir do comando $if()$ . A comparação pode ser explicada pelo seguinte exemplo: em uma sequência de termos $A, B, C$ e $D$ , o programa inicialmente declara $A$ como $n1$ e $B$ como $n2$ e caso a soma $S$ deles siga as restrições, soma-se 1 ao resultado final $R$ . Depois acontece o mesmo com os pares $(A,C)$ e $(A,D)$ , apenas alterando $n2$ para $C$ e posteriormente para $D$ . Em seguida, é o $n1$ que é alterado para $B$ para comparar os pares $(B,C)$ e $(B,D)$ , alterando $n2$ então para $C$ e $D$ . Por último, $n1$ vira $C$ e é comparado o par $(C,D)$ , sendo $n2$ equivalente a $D$ . E assim por diante caso existissem mais números nessa sequência.

Complexidade: $O(N)$

Segue o código comentado para melhor compreensão da solução:

	#include<bits/stdc++.h>//biblioteca utilizada
	using namespace std;
	#define MAXN 1000 //define MAXN como a abreviatura de 1000 (MAXN=1000)
	int V[MAXN]; //declaração de vetor
	int main()
	{
	int N,I,F,R,S,n1,n2; //declaração das demais variáveis
	scanf("%d %d %d", &N, &I, &F); //lê a primeira linha de entrada
	for(n1=0; n1<N; n1++) //loop para ler as variáveis da segunda linha de entrada
	{
	scanf("%d", &V[n1]); //lê a segunda linha de entrada
	}
	for(n1=0; n1<N-1; n1++) //parte 1 do loop para comparar um par de números
	{
	for(n2=n1+1; n2<N; n2++) //parte 2 do loop para comparar um par de números
	{
	S=V[n1] + V[n2]; //determina o valor de S (soma de um par de números)
	if(S>=I && S<=F) //verifica se a soma de um par está entre "I" e "F"
	{
	R++; //soma um no resultado final caso o par esteja entre "I" e "F"
	}
	}
	}
	printf("%d", R); //imprimi a resposta final
	return 0; //retorna a 0
	}

view raw

pares.cpp

hosted with ❤ by GitHub

Parcelamento sem Juros

Conhecimento prévio necessário:

Utilizamos as duas variáveis $V$ e $P$ para ler a entrada, $quo$ como o quociente da divisão de $V$ por $P$ ( $V/P$ ), $resto$ como o resto da divisão de $V$ por $P$ ( $V$ % $P$ ) e $cont$ como uma variável auxiliar para os loops responsáveis por imprimir os resultados

Para determinar quantas parcelas devem ser alteradas, ou seja, em quais deve ser adicionada uma parte do resto da divisão de $V$ por $P$ ou não, utilizamos dois loops a partir do comando $for()$ e da variável $cont$ . O número de parcelas que devem ser alteradas é equivalente ao $resto$ , então o primeiro loop imprimi $quo+1$ (parcela + resto) até $cont=resto$ . O segundo loop imprimi $quo$ (parcela normal) nas demais parcelas até $cont=P - resto$ (ou $P -$ número de parcelas alteradas).

Complexidade: $O(P)$

Segue o código comentado para melhor compreensão da solução:

	#include<bits/stdc++.h> //biblioteca utilizada
	using namespace std;
	int main()
	{
	int V,P,quo,resto,cont; //declaração das variáveis
	scanf("%d %d", &V, &P); //lê as variáveis de entrada
	quo = V/P; //quo assume o valor do quociente da divisão de V por P
	resto = V%P; //resto assume o valor do resto da divisão de V por P
	for(cont=0; cont<resto; cont++) //loop para adicionar o resto as parcelas necessárias
	{
	printf("%d \n", quo+1); //imprimi todas as saídas que têm alteração por conta do resto
	}
	for(cont=0; cont<P-resto; cont++) //loop para imprimir as parcelas que não sofrem nenhuma alteração
	{
	printf("%d \n", quo); //imprimi todas as saídas que NÃO têm alteração por conta do resto
	}
	return 0; //retorna a 0
	}

view raw

parcelamento.cpp

hosted with ❤ by GitHub

Manchas de Pele

Conhecimento prévio necessário:

Utilizamos as variáveis $N$ e $M$ para ler a primeira linha de entrada, as variáveis $i$ $j$ como variáveis auxiliares que irão dizer em qual pixel estamos (por exemplo o último pixel é o $pixel[8][9]$ ), o vetor de vetores $pixel[i][j]$ para salvar todos os demais números de entrada (1 ou 0) que correspondem aos pixels, a variável $manchas$ para contabilizar o número de manchas, os vetores auxiliares $va$ e $vb$ para ajudar a checar todos os vizinhos de um pixel a partir de suas coordenadas, $k$ , $newa$ e $newb$ como variáveis auxiliares para checar os 4 vizinhos de um pixel (cima,baixo,dir,esq) e montar um novo par de coordenadas caso um deles não tenha sido checado, uma fila para checar os pixels e seus vizinhos um a um, um bool de um vetor de vetores $visit[i][j]$ que determina se um pixel já foi analisado ou não e as variáveis $MAXN$ e $MAXM$ para definir o tamanho do vetor de algumas variáveis no início.

A ideia nesse problema é montar um $grafo$ a partir da imagem de números 0 ou 1 que é dada. Iniciamos lendo o tamanho dessa imagem pelo $N$ e $M$ , depois lemos todos os pixels por dois loops do comando $for()$ que comandam as coordenas desse pixel e, novamente com dois loops do comando $for()$ que comandam as coordenadas desse pixel e com uma condição pelo comando $if()$ , checamos se esse pixel ainda não foi analisado, mas faz parte de uma mancha. Se essa condição for satisfeita, soma-se 1 no resultado final $manchas$ e vamos para a $void BFS()$ , de acordo com o par de coordenadas do pixel que estamos vendo i e j, para analisar seus vizinhos atravessando todo o grafo.

Na $void BFS()$ , adicionamos os par de coordenadas no topo na fila e ficamos em loop enquanto essa fila não estiver vazia, comando ! $fila.empty()$ , atribuímos o valor do $i$ ao $a$ e o valor do $j$ ao $b$ e apagamos o par da fila (que já está salvo nas variáveis citadas). Em seguida começamos a checar seus 4 vizinhos (cima,baixo,dir,esq) a partir dos vetores auxiliares $va$ e $vb$ que possuem valores pré-definidos, que serão somados ao $a$ e ao $b$ formando novas variávies ( $newa$ e $newb$ ). Por fim, temos a condição de que se esse pixel vizinho ainda não foi analisado e é um pedaço de mancha (ou seja, 1), ele é definido com já analisado no vetor de vetores $visit[i][j]$ (=true) e é adicionado na fila para checar os seus vizinhos também para agilizar o processo de verificação.

Complexidade: $O(N*M)$

Segue o código comentado para melhor compreensão da solução:

	#include<bits/stdc++.h> //biblioteca utilizada
	using namespace std;

	const int MAXN=1100, MAXM=1100; //declara o valor de MAXN e MAXM (máximo de N e M), que define o tamanho de outros vetores
	int pixel[MAXN][MAXM]; //declara um vetor(pixel) de coordenada (MAXN,MAXM)
	bool visit[MAXN][MAXM]; //declara uma função para saber se um pixel já foi (true/0) ou não (false/1) analisado

	int va[4]={1,0,-1,0}; //declara um vetor já com os valores de cada posição do vetor
	int vb[4]={0,1,0,-1}; //declara um vetor já com os valores de cada posição do vetor

	void BFS(int i, int j)
	{
	int a,b,k,newa,newb; //declara as variáveis utilizadas no BFS
	queue<pair<int,int> > fila; //declara um queue (fila) do tipo pair que armazena dois inteiros (2 int)
	fila.push(make_pair(i,j)); //insere o par (i,j) na fila
	visit[i][j]=true; //determina a bool como true (verdade ou 0)
	while(!fila.empty()) //enquanto exitir elementos na fila (enquanto ela não estiver vazia)
	{
	a=fila.front().first; //a assume o valor do primeiro termo (i) do par na primeira posição da fila
	b=fila.front().second; //b assume o valor do segundo termo (j) do par na primeira posição da fila
	fila.pop(); //remove o primeiro elemento da fila, ou seja, o primeiro par é apagado (mas está salvo em a e b)
	for(k=0; k<4; k++) //k começa em 0 e enquanto é menor que quatro, ficamos nesse loop; no fim sempre é somado 1 na variável k
	{
	newa = a + va[k]; //newa assume o valor de a + o valor da posição 'k' no vetor de a 'va'
	newb = b + vb[k]; //newb assume o valor de b + o valor da posição 'k' no vetor de b 'vb'

	if(!visit[newa][newb] && pixel[newa][newb]) //se ainda não analisamos esse vizinho E ele é um pedaço de mancha (ou seja, na entrada ele seria 1)
	{
	visit[newa][newb]=true; //determina o vetor desse pixel como verdade, ou seja, como um pixel já analisado
	fila.push(make_pair(newa,newb)); //insere esse novo par de coordenadas na fila para depois analisar os seus pixels vizinhos também
	}
	}
	}
	}

	int main()
	{
	int N,M,i,j,manchas=0; //declara as variáveis utilizadas na main()
	scanf("%d %d", &N, &M); //lê a primeira linha de entrada (M e N)
	for(i=1; i<=N; i++) //i começa sendo 1 e enquanto não é igual a N, ficamos nesse loop; no fim é somado 1 na variável i
	{
	for(j=1; j<=M; j++) //j começa sendo 1 e enquanto não é igual a M, ficamos nesse loop; no fim é somado 1 na variável j
	{
	scanf("%d", &pixel[i][j]); //lê todos os inteiros P, ou seja, os pixels (0 ou 1)
	}
	}
	for(i=1; i<=N; i++) //i começa sendo 1 e enquanto não é igual a N, ficamos nesse loop; no fim é somado 1 na variável i
	{
	for(j=1; j<=M; j++) //j começa sendo 1 e enquanto não é igual a M, ficamos nesse loop; no fim é somado 1 na variável j
	{
	if(!visit[i][j] && pixel[i][j]==1) //se esse pixel ainda não foi analisado E é um pedaço de mancha
	{
	manchas++; //soma 1 na variável manchas, ou seja, conta mais uma mancha na imagem
	BFS(i,j); //observamos os pixels vizinhos desse pixel, ou seja, vamos para a void BFS()
	}
	}
	}
	printf("%d\n", manchas); //imprimi a resposta final = número de manchas
	return 0; //retorna a 0
	}

view raw

Manchas.cpp

hosted with ❤ by GitHub