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

Comentário por Bia Cunha

Para ver o caderno de tarefas da Segunda Fase da Programação Nível 2 da OBI 2017, clique aqui.

Dario e Xerxes

Conhecimento prévio necessário:

Estruturas condicionais (Aula 2)
Estruturas de repetição (Aula 2)

A fim obter a resposta, precisamos saber quem ganhou a cada partida, contando em duas variáveis, d e x. O contador de maior valor representa o vencedor. Existem várias formas de saber quem ganhou, como checar cada possibilidade com vários if’s. Porém, observe que se x é uma unidade maior que d, Darios ganha (d=1 e x=2, por exemplo). Para incluir o caso em que 4 ganha de 0, podemos dizer que sempre que d+1 dividido por 5 tem resto igual a x. Com um raciocínio parecido, temos que sempre que d+2 dividido por 5 tem resto igual a x, d ganha. Essas duas condições cobrem todos os casos em que D ganha. Segue código para melhor entendimento.

	// Dario e Xerxes - F2P2 - OBI 2017
	// Bia Cunha
	// Complexidade: O(n)
	#include <bits/stdc++.h>

	using namespace std;

	//declara as variáveis descritas na questão
	int n;
	int d, x;

	//e a quantidade de vitórias de Dario e Xerxes
	int qtd_d, qtd_x;


	int main(){
	//lê a quantidade de partidas
	scanf("%d", &n);

	//inicializa como 0 a quantidade de vitórias de ambos os jogadores
	qtd_d=0;
	qtd_x=0;

	for(int i=0; i<n; i++){
	//lê o número colocado por cada um na rodada
	scanf("%d %d", &x, &d);

	//checa qual ganhou
	if((x == (d+1)%5) \|\| (x == (d+2)%5))
	qtd_d++;

	else
	qtd_x++;
	}

	//se a quantidade de vitórias de dario for maior, imprime seu nome
	if(qtd_d > qtd_x) printf("dario\n");

	//se não, xerxes ganhou
	else printf("xerxes\n");

	return 0;
	}

view raw

xerxes.cpp

hosted with ❤ by GitHub

Frete

Conhecimento prévio necessário:

Menor caminho (Aula 10)

Como é ilustrado na questão, as cidades podem ser representadas como vértices de um grafo, e as “entregas diretas” como arestas. Sendo o custo para transportar uma encomenda entre duas cidades vizinhas o peso de cada aresta, a resposta pode ser obtida com um algoritmo de menor caminho, como o algoritmo de Floyd-Warshall, de complexidade O(n³). Segue o código para melhor entendimento.

https://gist.github.com/e53e631411952ea2099720545aa73634.git

	#include <bits/stdc++.h>

	//define MAX e INF
	#define INF 0x3f3f3f3f
	#define MAX 110

	using namespace std;

	//declara as variáveis decritas no problema
	int n, m;
	int a, b, c;

	//e a matriz de adjacência
	int dist[MAX][MAX];

	void floyd(){
	for(int k=1; k<=n; k++)
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
	dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
	}

	int main(){
	//lê a quantidade de vértices e arestas
	scanf("%d %d", &n, &m);

	//inicializa as distâncias entre os vértices como infinito
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
	dist[i][j]=INF;

	for(int i=0; i<m; i++){
	//lê as arestas
	scanf("%d %d %d", &a, &b, &c);

	//e atualiza os pesos na matriz
	dist[a][b]=c;
	dist[b][a]=c;
	}

	//algoritmo de Floyd-Warshall
	floyd();

	//imprime a menor distância entre 1 e n
	printf("%d\n", dist[1][n]);
	}

view raw

frete.cpp

hosted with ❤ by GitHub

https://gist.github.com/biacunha/e53e631411952ea2099720545aa73634#file-frete-cpp

Mapa

Conhecimento prévio necessário:

Flood Fill (Aula 9)

Há apenas uma rota entre as posições inicial e final de Hermione. Podemos então localizar a posição marcada com o ‘o’ e fazer uma DFS a partir daí para saber qual a última marcada com um ‘H’ a qual conseguimos chegar. Segue código.

	// Mapa - F2P2 - OBI 2017
	// Bia Cunha
	// Complexidade: O(n)

	#include <bits/stdc++.h>

	#define MAX 110

	using namespace std;

	//declara l e c
	int l, c;

	//as viriáveis que guardarão as coordenadas da origem
	int ori_x, ori_y;

	//os vetores de direção
	int dir_x[4]={1,-1,0,0};
	int dir_y[4]={0,0,1,-1};

	//matriz que guarda a entrada
	int mat[MAX][MAX];

	//matriz que marca quais casas já foram visitadas
	int vis[MAX][MAX];

	int dfs(int a, int b){
	//check será true se o final do caminho for em (a, b)
	bool check=true;

	//marco que visitei (a, b)
	vis[a][b]=true;

	//teste cada uma das direções nas quais o caminho pode continuar
	for(int k=0; k<4; k++){
	int x=a+dir_x[k];
	int y=b+dir_y[k];

	//se esse vizinho ainda não foi visitado e ele faz parte do caminho
	if(!vis[x][y] && mat[x][y]=='H'){
	//marca que o caminho não acabou
	check=false;

	//chama a DFS para esse vizinho
	dfs(x, y);
	}
	}

	//se esse é o fim do caminho, imprime as coordenadas
	//é garantido pelo enunciado que isso só ocorrerá uma vez
	if(check) printf("%d %d", a, b);
	}

	int main(){
	//lê a quantidade de linhas e colunas
	scanf("%d %d", &l, &c);

	//inicializa as bordas da matriz como obstáculos
	//dessa forma, é garantido que a DFS não passará dos limites estabelecidos
	for(int i=0; i<=l+1; i++) mat[i][0]=mat[i][c+1]='.';
	for(int i=0; i<=c+1; i++) mat[0][i]=mat[l+1][i]='.';

	//lê os caracteres
	for(int i=1; i<=l; i++)
	for(int j=1; j<=c; j++){
	scanf("%d", &mat[i][j]);

	//se essa é a origem, salva as coordenadas
	if(mat[i][j]=='o')
	ori_x=i, ori_y=j;
	}

	//começa a dfs a partir da origem
	dfs(ori_x, ori_y);
	}

view raw

mapa.cpp

hosted with ❤ by GitHub

Cortando papel

Conhecimento prévio necessário:

Vector e pair (Aula 10)

A solução mais ingênua para essa questão é testar todas as alturas possíveis em que se pode cortar o papel, subindo a linha de corte. Essa ideia não passaria no tempo, pois a complexidade é O(H), e H tem valor máximo 10^9. Porém, não é necessário checar todas as alturas, pois quantidade de pedaços só muda quando passamos do topo de alguns retângulos específicos. Perceba que se a cortarmos a figura próximo à base, ela será dividida em dois:

Esse é o menor número de pedaços que conseguimos com um corte. Se cortarmos logo acima do retângulo 9 (sendo o primeiro numerado 1), o menor, o número de pedaços aumenta para três.

Porém, não há diferença entre cortar acima dos retângulos 2 e 13 ou cortar acima do 3, ambos resultam em seis pedaços.

Isso porque o 2 e o 13, assim como o 9 e o 11, são vales: um retângulo ou série de retângulos adjacentes com menor altura que ambos os seus vizinhos. Se a linha de corte for subindo pela imagem, toda a vez que passar por um vale, a quantidade de pedaços aumenta em 1, pois o que era um só pedaço agora está separado pelo vale.

Observe que quando a linha passa de um pico, ou seja, um retângulo ou série de retângulos adjacentes com maior altura que ambos os seus vizinhos, a quantidade de pedaços diminui em um:

A quantidade de pedaços de papel só muda quando a linha de corte passa por picos ou vales.

Para obter a melhor resposta, podemos primeiro salvar as alturas lidas na entrada h em um vetor, chamado aqui de retangulos. Sabendo que retângulos adjacentes de mesma altura fazem parte do mesmo pico ou vale, vamos salvar apenas os que não são iguais ao último adicionado (if(h != retangulos.back()) retangulos.push_back(h);). Também por praticidade, adicionamos um elemento 0 no começo e no final do vetor. Assim, podemos comparar a primeira e a última altura h com os elementos anteriores e seguintes sem problemas.

Os retângulos que nos interessam são os picos e vales. Criamos um vetor pv que guarda os retângulos com essas características. Cada elemento terá um par de inteiros formado pela altura do retângulo e 1 ou -1, assinalando se ele é pico ou vale respectivamente.

Então, criamos uma variável qtd, que guarda a quantidade de pedaços de papel. Em seguida, passamos por cada pv em ordem crescente de altura (basta ordenar pelo primeiro elemento antes de percorrer), atualizando qtd de acordo com os picos e vales encontrados (qtd+=retangulos[i].second). Para conseguir a resposta, basta ter uma variável maior que guarda o maior valor de qtd até então (maior=max(maior, qtd)).

	// Papel - F2P2 - OBI 2017
	// Bia Cunha
	// Complexidade: O(nlog)

	#include <bits/stdc++.h>
	#define MAXN 100010

	using namespace std;

	int n;
	int h;
	vector<int> retangulos;
	map<int, int> m;
	map<int, int> ::iterator it;

	int main(){
	//lê a quantidade de retângulos
	scanf("%d", &n);

	//adiciona 0 no início
	retangulos.push_back(0);

	for(int i=0; i<n; i++){
	//lê novo retângulo
	scanf("%d", &h);

	//se ele é diferente
	if(h != retangulos.back()) retangulos.push_back(h);
	}

	//adiciona 0 no final
	retangulos.push_back(0);

	for(int i=1; i<retangulos.size()-1; i++){
	//se o retângulo i é um pico, ou seja, maior que o anterior e que o seguinte,
	if(retangulos[i] > retangulos[i-1] && retangulos[i] > retangulos[i+1])
	//salva em pv como pico (-1)
	pv.push_back( make_pair(retangulos[i], -1) );

	//se o retângulo i é um vale, ou seja, maior que o anterior e que o seguinte,
	if(retangulos[i] < retangulos[i-1] && retangulo[i] < retangulos[i+1])
	//salva em pv como vale (+1)
	pv.push_back( make_pair(retangulos[i], 1) );
	}

	//qtd começa como 2
	int qtd, resp;
	qtd=resp=2;

	for(it=m.begin(); it!=m.end(); it++){
	//somo o que tiver na altura atual
	qtd+=it->second;

	//atualiza a resposta
	resp=max(resp, qtd);
	}

	//imprime a resposta
	printf("%d\n", resp);
	}

view raw

papel.cpp

hosted with ❤ by GitHub