Comentário NOIC OBI 2017 - Fase 2 - Programação Nível 1

Comentário por João Guilherme

Montanha

Conhecimento prévio necessário:

Entrada e saída (Aula 1)
Estruturas condicionais e repetição (Aula 2)

Primeiro lemos o $n$ , em seguida usamos um for para armazenarmos os números. Usaremo um vetor $v$ de tamanho 1024, sendo assim maior que o $n$ máximo. Uma vez tendo lido todas as variáveis, usamos outro for, indo de 2 até $n - 1$ checamos para cada elemento $v[i]$ do vetor se $v[i - 1] > v[i] < v[i + 1]$ . Se isso ocorrer alguma vez, imprimimos S e terminamos o programa, porém se o loop terminar imprimimos N.

	#include <bits/stdc++.h>

	using namespace std;

	int v[1024];

	int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i){
	cin >> v[i];
	}
	for(int i = 2; i <= n - 1; ++i){
	if(v[i] < v[i - 1] && v[i] < v[i + 1]){
	printf("S\n");
	return 0;
	}
	}
	printf("N\n");

	return 0;
	}

view raw

montanha.cpp

hosted with ❤ by GitHub

Jogo de Tabuleiro

Conhecimento prévio necessário:

Entrada e saída (Aula 1)
Estruturas condicionais e repetição (Aula 2)

Primeiro lemos o $n$ , em seguida usamos dois for, um dentro do outro para lermos as cores das pedras no tabuleiro. Usaremo uma matriz $mat$ de tamanho 128 por 128, tendo portanto dimensões maiores que o $n$ máximo. A seguir usamos dois for para preencher a tabela, ambos começando do 2 e indo até o $n$ . Em cada célula da matriz analisamos as células: acima, a logo abaixo e a na diagonal, se a soma delas for maior que 1, então existem mais pretas que brancas e sua cor será branca, ja se a soma for menor ou igual a 1 existem mais brancas que pretas e a celula deve ser preta.

Segue o código para melhor entendimento

	#include<bits/stdc++.h>

	using namespace std;

	int mat[128][128];

	int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= n; ++j)
	cin >> mat[i][j];
	for(int i = 2; i <= n; ++i)
	for(int j = 2; j <= n; ++j){
	if(mat[i - 1][j] + mat[i][j - 1] + mat[i - 1][j - 1] > 1) mat[i][j] = 0;
	else mat[i][j] = 1;
	}
	cout << mat[n][n] << "\n";
	return 0;
	}

view raw

jogop1f2.cpp

hosted with ❤ by GitHub

Castelos da Nlogônia

Conhecimento prévio necessário:

Grafos II: Flood Fill (Aula 9)

Nessa questão devemos usar uma busca em profundiade para percorrer nossa árvore toda vez que for necessário fazer uma pintura. Em nossa dfs, guardamos uma bool paint, que vai nos dizer se o vértice analisado deve ser pintado, ou seja, se o vértice em questão está no caminho entre os vérices u e v. Para fazer isso basta nós termos em mente as seguintes coisas:

mark[128] será um vetor que vai dizer se o vértice em questão foi analisado nessa dfs, assim marcamos os vértices com um número t que cresce para cada dfs que fazemos.
Caso de base: Se u == v, então pintamos v e retornamos 1.
Se não, paint vai receber o or do retorno de cada dfs dos filhos do u, assim se algum filho conseguir alcansar o v paint se tornará igual a 1 (pois 1 or 0 = 1). Por fim pintamos o vértice se paint for verdadeiro e retornamos paint.

Segue o código para melhor entendimento.

	#include<bits/stdc++.h>

	using namespace std;

	vector <int> adj[128];
	int colour[128], mark[128], t;

	bool dfs(int u, int v, int c){
	bool paint = 0;
	mark[u] = t;
	if(u == v){
	colour[v] = c;
	return 1;
	}
	for(int i = 0; i < adj[u].size(); ++i)
	if(mark[adj[u][i]] != t) paint \|= dfs(adj[u][i], v, c);
	if(paint) colour[u] = c;
	return paint;
	}

	int main(){
	int n, m, u, v, c;
	cin >> n >> m;
	for(int i = 1; i < n; ++i){
	cin >> u >> v;
	adj[u].push_back(v), adj[v].push_back(u);
	}
	for(int i = 0; i < m; ++i){
	cin >> u >> v >> c;
	++t;
	dfs(u, v, c);
	}

	for(int i = 1; i <= n; ++i) cout << colour[i] << " ";
	cout << "\n";
	return 0;
	}

view raw

coresp1f2.cpp

hosted with ❤ by GitHub