Prova da OPI 2010

Demorei, mas cumpri. Estou disponibilizando, em primeira mão, a prova da Olimpíada Paraibana de Informática (OPI) para download. A prova está em formato .pdf, se quiser baixá-la, clique com o botão direito do mouse na palavra “PROVA” e escolha a opção “Salvar link como…”, pois se você apenas clicar no link, o arquivo vai abrir no próprio navegador.

As respostas são da equipe Koderov (UFCG) e foram disponibilizadas por Philippe Targino. Todas elas foram escritas em C++.

PROVA

RESPOSTAS

Problema A:
/*

Problema A - Programa para NASA

A abordagem usada para essa questão foi a seguinte: Para cada '{'
incrementa-se o contador, e para cada '}' decrementa-se. Caso o contador
esteja em 0 e precise ser decrementado, significa um erro. Registra-se
o erro, transforma o '}' num '{', alterando o contador para 1 agora.
O resultado será o número de erros registrados, mais metade do valor do
contador ao final (pois metade dos '{' terão de ser transformados em '}')
para parear entre si.

*/

#include <cstdio>
#include <cstring>

int main() {
	char line[2001];

	int t = 0;
	while (true) {
		scanf("%s", line);

		if (line[0] == '-')
			break;
		int result = 0, noleft = 0;

		for (int i = 0; i < strlen(line); i++) {
			if (line[i] == '{')
				noleft++;
			if (line[i] == '}') {
				if (noleft)
					noleft--;
				else {
					result++;
					noleft = 1;
				}
			}
		}

		printf("%d. %d\n", ++t, result + noleft / 2);
	}
}
Problema B:
/*

Problema B - Reforma no Telhado

Simples questão de MDC. Para descobrir o número mínimo de telhas,
basta calcular o mdc das dimensões, dividir cada uma delas pelo
mdc e multiplicar os resultados entre si.

*/

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

long long  mdc(long long a, long long b){
	if(a > b)
		return mdc(b,a);
	if (a == 0)
		return b;
	return  mdc(b%a, a);

}

int main(){
	long long a, b;
	while(scanf("%lld%lld", &a, &b) && a && b) {
		long long ans = (a*b)/(mdc(a,b)*mdc(a,b));
		printf("%lld\n", ans);
	}
}
Problema C:
/*

Problema C - O Mágico

Questão de simulação, basta seguir os passos determinado pela questão

*/

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
	long long n0, n1, n2, n3, n4, n5;
	bool ehImpar;
	int count = 1;
	while(scanf("%lld", &n0) && n0) {
		n1 = 3 * n0;
		if(n1%2){
			ehImpar = true;
			n2 = (n1+1)/2;
		}else{
			ehImpar = false;
			n2 = n1/2;
		}
		n3 = 3*n2;
		n4 = n3/9;
		printf("%d. %s %lld\n", count++, ehImpar? "impar":"par", n4);

	}
}
Problema D:
/*

Problema D - Ataque a Base de Dunga

Cria-se dois vetores, um para cada torre, com a área mínima necessária
para que a torre possa encobrir cada ponto e o id do ponto, e ordena-os
com base nessa área necessária (área de círculo: PI*Raio^2). Então,
percorre-se o vetor da torre 1, um i que vai de 0 até n. A área do i-ésimo
elemento é suficiente para cobrir os elementos do intervalo [0,i]. Contabiliza
esses elementos, e subtrai a área necessária da área total. Para a torre 2,
contabiliza-se os elementos com área menor que a restante. O ideal é usar
um Set para isso, pois pode haver contagem repetida de pontos. Encontra o
resultado que cobre mais pontos, e pronto🙂

*/

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef pair<double, int> ponto;

double area(double xt, double yt, double x, double y) {
	return 3.141 * ( (xt - x) * (xt - x) + (yt - y) * (yt - y) );
}

int main() {

	double dx1, dy1, dx2, dy2, dt, dx, dy;

	int n, t = 0;
	while (scanf("%d", &n), n) {
		scanf("%lf %lf %lf %lf %lf", &dx1, &dy1, &dx2, &dy2, &dt);

		vector<ponto> torre1, torre2;

		for (int i = 0; i < n; i++) {

			scanf("%lf %lf", &dx, &dy);

			torre1.push_back(make_pair(area(dx1, dy1, dx, dy), i));
			torre2.push_back(make_pair(area(dx2, dy2, dx, dy), i));
		}

		sort(torre1.begin(), torre1.end());
		sort(torre2.begin(), torre2.end());

		int best = n;
		int count = 0;
		for (int k = 0; k < n; k++) {
			if (dt < torre2[k].first)
				break;
			count++;
		}

		best = min(best, n - count);

		for (int i = 0 ; i < n; i++) {

			double areaAtual = torre1[i].first;

			if (areaAtual > dt)
				break;

			set<int> defendidos;

			for (int j = 0; j <= i; j++)
				defendidos.insert(torre1[j].second);

			double areaRestante = dt - areaAtual;

			for (int j = 0; j < n; j++) {
				if (areaRestante < torre2[j].first)
					break;
				defendidos.insert(torre2[j].second);
			}

			best = min(best, n - (int) defendidos.size());
		}

		printf("%d. %d\n", ++t, best);
	}

	return 0;
}
Problema E:
Problema E - Superstição de Rubinho

Aqui basta encontrar o 3º maior elemento de um array de 10 elementos.
Como a posição é próxima da maior (ou menor, se fosse o caso),
comparações com 3 variáveis (primeiro, segundo e terceiro) são suficientes

*/

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
	int n, pri, seg, ter, m, num;

	scanf("%d", &n);

	for(int i=0; i<n; i++){
		pri = 0;
		seg=0;
		ter=0;

		scanf("%d", &m);
		for(int k=0; k<10; k++){
			scanf("%d", &num);
			if(num > ter){
				ter = num;
				if(num > seg){
					ter = seg;
					seg = num;
					if(num > pri){
						seg = pri;
						pri = num;
					}
				}
			}

		}
		printf("%d %d\n", m, ter);

	}
	return(0);
}
Problema F:
/*

Problema F - Brincando de Revestrez

Como esse problema foi lido/feito exclusivamente pelos outros
membros da equipe, não tenho como comentar nada.

*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <iostream>

using namespace std;

typedef pair<int, bool> carta;

int lime, limd, n;
vector<carta> mesa[101], tmp;
char c;

void junta(int p1, int p2){
	carta car;

	for(int i=(int) mesa[p1].size()-1; i>=0; i--){
		car = make_pair(mesa[p1][i].first, !mesa[p1][i].second);
		mesa[p2].push_back(car);
	}
}

int main() {
	int t = 0;

	while(scanf("%d\n", &n) != EOF, n!=0){
		for(int i=1; i<=n; i++){
			c = '0';
			while((c != 'C') && (c != 'B')) scanf("%c", &c);
			carta car = make_pair(i, (c == 'C'));
			mesa[i].clear();
			mesa[i].push_back(car);
		}

		lime = 1;
		limd = n;
		for(int i=1; i<=n-1; i++){
			c = '0';
			while((c != 'D') && (c != 'E'))
				scanf("%c", &c);
			if(c == 'D'){
				junta(limd,limd-1);
				limd--;
			}else{
				junta(lime,lime+1);
				lime++;
			}
		}

		int m;
		scanf("%d", &m);
		int caso;

		printf("Pilha %d\n", ++t);

		for(int i=0; i<m; i++){
			scanf("%d", &caso);
			caso = n - caso;

			if(mesa[limd][caso].second)
				printf("Carta %d virada pra cima %d.\n", n - caso, mesa[limd][caso].first);
			else
				printf("Carta %d virada pra baixo %d.\n", n - caso, mesa[limd][caso].first);
		}
	}

	return 0;
}
Problema G:
/*

Problema G - Desktop

Geometria computacional. Basta percorrer os pontos por todos as janelas
(retangulos), imprimir em quais ele está contido (função bate(ponto, janela) abaixo)
e imprimir o resultado, ou "background", caso não bata com nenhum.

*/

#include <cstdio>
#include <vector>

using namespace std;

typedef pair<int, int> ponto;
typedef pair<ponto, ponto> janela;

bool bate(ponto p, janela j) {
	if (p.first < j.first.first || p.first > j.second.first)
		return false;
	if (p.second < j.first.second || p.second > j.second.second)
		return false;
	return true;
}

int main() {

	int caso = 1, n, r, c, w, h, m;
	while (scanf("%d", &n), n) {
		vector<janela> lista;
		for (int i = 0; i < n; i++) {
			scanf("%d %d %d %d", &r, &c, &w, &h);
			lista.push_back(make_pair( make_pair(r, c), make_pair(r + h - 1, c + w - 1) ) );
		}

		printf("Desktop %d:\n", caso++);

		scanf("%d", &m);

		for (int i = 0; i < m; i++) {
			scanf("%d %d", &r, &c);
			ponto p = make_pair(r, c);
			for (int j = n - 1; j >= 0; j--) {
				if (bate(p, lista[j])) {
				 	printf("janela %d\n", j + 1);
				 	break;
				}

				if (j == 0)
					printf("background\n");
			}
		}

	}

	return 0;
}
Problema H:
/*

Problema H - Emails do FBI

A idéia desse algoritmo é verificar, dado uma sequência de dígitos,
se há uma próxima permutação e qual é. Em C++, existe a função next_permutation(),
que modifica um vetor de elementos comparáveis para sua próxima permutação,
e retorna true ou false, dependendo se há uma próxima permutação.
Fazer isso na mão é simples e fácil de achar na internet.

*/
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
	int t;
	char num[81];
	scanf("%d", &t);
	for(;t;t--){
		int a;
		scanf("%d%s", &a, num);
		int lenght = strlen(num);
		if(next_permutation(num, num+lenght))
			printf("%d %s\n", a, num);
		else
			printf("%d %s\n", a, "ERRO");
	}
}
Problema I:
/*

Problema I - Subsequencias Divisíveis

Por questão de dimensões das variáveis, gerar todas as subsequências
possíveis é algo inviável. Mas podemos tirar proveito do seguinte:
Se (a % c = d) e (b % c = d), então a - b será múltiplo de c
(logo, divisível por c). Então, se o somatório de uma subsequencia [1, k]
dividido por c tem resto d, e o somatório de uma subsequencia [1, n],
tem também resto d quando dividido por c, então o somatório da
subsequencia [k+1, n] é, obrigatóriamente, divisível por c. Então,
se eu tenho x somatórios de subsequencias diferentes [1,k] com resto d,
combinando esses 2 a 2, teremos x(x-1)/2 combinações divisíveis por c.
Como o divisor vai até 1 milhão, basta criar um array de mesmo tamanho,
com contadores para tais subsequencias, e depois fazer o somatório
das combinações 2 a 2 de cada contador. Lembrando que para resto 0,
eu tenho possibilidades também sem subtrair, pois o próprio [1,k] é
divisível por c.

*/

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
	int t, resto, num, d, n;
	long long a[1000000], result;

	scanf("%d", &t);

	while (t--) {
		scanf("%d %d", &d, &n);

		resto = 0;
		for (int i = 0; i < d; i++)
			a[i] = 0;

		a[0] = 1;
		for (int i = 0; i < n; i++) {
			scanf("%d", &num);
			resto = (resto + num) % d;
			a[resto]++;
		}

		result = 0;
		for (int i = 0; i < d; i++) {
			result += (a[i] * (a[i] - 1)) / 2;
		}

		printf("%lld\n", result);
	}

	return 0;
}

Se você achou estas questões muito difíceis, tente resolver estas mais fáceis: Questões de aquecimento

Acesse o novo endereço do Olá Mundo!: http://ola-mundo.com

  1. Gemilson
    12 de junho de 2012 às 21:20

    Caro Luiz Augusto, parabéns pelo blog, sou prof. de informática, gostaria de utilizar alguns materiais de seu blog em aulas minhas, citando a referencia é claro, e gostaria de uma dica sua, onde consigo outras provas de OPIs passadas?

    • 12 de junho de 2012 às 21:35

      Gemilson,
      Não sei lhe informar onde encontrar as provas das OPIs passadas. Acho que elas não são divulgadas oficialmente.
      Eu tive acesso a estas, pois participei da olimpíada.

      Com relação a utilizar materiais deste blog, fique à vontade. Fico muito feliz que eles estão sendo úteis.
      Para encontrar mais materiais de minha autoria, acesse minha conta do slideshare: https://www.slideshare.net/LuizAugustoMacdoMorais/.

  1. No trackbacks yet.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: