Alguns algoritmos da Regional da Maratona da ACM 2007

Posted by sippert | Filed under algoritmos, eventos

Nesse ano de estréia resolvemos apenas dois algoritmos simples utilizando-se da linguagem C++, esperamos que nos próximos anos consigamos melhores resultados.

O primeiro problema resolvido foi o “Histórico de Comandos”, que consistia em dizer quantas vezes o usuário precisa teclar a tecla “seta para cima” em cada entrada. Abaixo o algoritmo:

#include <iostream>
using namespace std;
int n=0,y=0;
int vet[1000000];
int esta(int num){
	for(int j=(y-1);j>-1;j--)
		if(vet[j]==num)
			return (y-j);
	return (-1);
}
int main() {
	while((cin >> n)and(n!=0)){
		int soma=0,a=0,b=0;
		y=0;
		for(int i=0;i<n;i++)
			vet[i]=0;
		for(int i=0;i<n;i++){
			cin >> a ;
			b = esta(a);
			if(b>-1)
				soma+=b;
			else
				soma+=a+y;
			vet[y]=a;
			y++;
		}
		cout << soma << endl;
	}
	return 0;
}

O segundo algoritmo foi o “Jogo das Varetas”, em que deve-se descobrir o número de retângulos que podem ser formados com as varetas existentes. Abaixo o algoritmo:

#include <iostream>
using namespace std;
int main() {
	int n=0;
	while((cin >> n)and(n!=0)){
		int soma=0,a=0,b=0;
		for(int i=0;i<n;i++){
			cin >> b >> a;
			soma += a/2;
		}
		soma = soma/2;
		cout << soma << endl;
	}
	return 0;
}

Compartilhe: