Solução dos Problemas da OBI2005

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Agora que eu acho que todas as escolas já submeteram as soluções dos problemas da Programação Nível 1 da OBI desse ano, estou publicando minhas quatro soluções, em C.

Frota de Táxi

//Frota de Taxi - OBI2005
#include <stdio.h>
 
int main() {
	float a, g, ra, rg, al, ga;
 
	scanf("%f %f %f %f", &a, &g, &ra, &rg);
	al=a/ra;
	ga=g/rg;
 
	if (al<ga) {
		printf("A\n");
	} else {
		printf("G\n");
	}
 
	return 0;
}

Campo de Minhocas

//Campo de Minhocas - OBI2005
#include <stdio.h>
#define NMAX 102
#define NMAX 102
 
int main() {
	int n, m, soma, i, j, matriz[NMAX][NMAX], maior=0;
 
	scanf("%d %d", &n, &m);
 
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			scanf("%d", &matriz[i][j]);
		}
	}
 
	for (i=1; i<=n; i++) {
		soma=0;
		for (j=1; j<=m; j++) {
			soma+=matriz[i][j];
		}
		if (soma>maior) {
			maior=soma;
		}
	}
 
	for (i=1; i<=m; i++) {
		soma=0;
		for (j=1; j<=n; j++) {
			soma+=matriz[j][i];
		}
		if (soma>maior) {
			maior=soma;
		}
	}
 
	printf("%d\n", maior);
 
	return 0;
}

Duende Perdido

//Duende Perdido - OBI2005
#include <stdio.h>
#include <values.h>
#define NMAX 102
 
int menor=MAXINT, p[NMAX][NMAX], custo[NMAX][NMAX];
 
int duende(int x, int y, int cus, int ox, int oy) {
 
	if (p[x][y]==1||p[x][y]==3) {
		if (cus<custo[x][y]) {
			custo[x][y]=cus;
			if ((x!=ox||y+1!=oy)&&p[x][y+1]!=-1) {
				duende(x, y+1, cus+1, x, y);
			}
			if ((x+1!=ox||y!=oy)&&p[x+1][y]!=-1) {
				duende(x+1, y, cus+1, x, y);
			}
			if ((x!=ox||y-1!=oy)&&p[x][y-1]!=-1) {
				duende(x, y-1, cus+1, x, y);
			}
			if ((x-1!=ox||y!=oy)&&p[x-1][y]!=-1) {
				duende(x-1, y, cus+1, x, y);
			}
		}
	}
	if (p[x][y]==0) {
		if (cus<custo[x][y]) {
			custo[x][y]=cus;
		}
		if (custo[x][y]<menor) {
			menor=custo[x][y];
		}
	}
}
 
int main() {
	int n, m, ix, iy, i, j;
 
	scanf("%d %d", &n, &m);
 
	for (i=0; i<=n+1; i++) {
		for (j=0; j<=m+1; j++) {
			p[i][j]=-1;
			custo[i][j]=MAXINT;
		}
	}
 
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			scanf("%d", &p[i][j]);
			if (p[i][j]==3) {
				ix=i;
				iy=j;
			}
		}
	}
 
	duende(ix, iy, 0, 0, 0);
 
	printf("%d\n", menor);
 
	return 0;
}

Trilhas

//Trilhas - OBI2005
#include <stdio.h>
#include <values.h>
#define NMAX 102
#define MMAX 1001
 
int main() {
	int campeao, n, m[NMAX], a[NMAX][MMAX], saida=0, i, j, parou, subir[NMAX], descer[NMAX], menor=MAXINT;
 
	scanf("%d", &n);
	for (i=1; i<=n; i++) {
		scanf("%d", &m[i]);
		for (j=1; j<=m[i]; j++) {
			scanf("%d", &a[i][j]);
		}
	}
 
	//Primeiro vamos ver se precisa haver esforço de subida
	for (i=1; i<=n; i++) {
		parou=0;
		for (j=1; j<=m[i]; j++) {
			//printf("%d %d\n", i, j);
			if (a[i][j]>a[i][j+1]&&j!=m[i]) {
				parou=1;
				//printf("parou!\n");
				j=m[i];
			}
		}
		if (!parou) {
			//Então vamos parar por aí...
			printf("%d\n", i);
			return 0;
		}
	}
 
	//A mesma coisa ao contrário
	for (i=1; i<=n; i++) {
		parou=0;
		for (j=m[i]; j>=1; j--) {
			//printf("%d %d\n", i, j);
			if (a[i][j]>a[i][j-1]&&j!=1) {
				parou=1;
				//printf("parou!\n");
				j=1;
			}
		}
		if (!parou) {
			//Então vamos parar por aí...
			printf("%d\n", i);
			return 0;
		}
	}
 
	//Não deu...
	//Vamos contar quantos metros vamos ter que subir (ou descer=subir ao contrário)
	for (i=1; i<=n; i++) {
		descer[i]=0;
		subir[i]=0;
		for (j=1; j<=m[i]; j++) {
			if (a[i][j]>a[i][j+1]) {
				descer[i]+=(a[i][j]-a[i][j+1]);
			} else {
				subir[i]+=(a[i][j+1]-a[i][j]);
			}
		}
	}
 
	//E quem sobe ou desce menos?
	for (i=1; i<=n; i++) {
		if (subir[i]<menor) {
			menor=subir[i];
		}
		if (descer[i]<menor) {
			menor=descer[i];
		}
	}
 
	//Mas peraí... Temos que ver o primeiro na ordem de identificação!
	for (i=1; i<=n; i++) {
		if (subir[i]==menor||descer[i]==menor) {
			printf("%d\n", i);
			return 0;
		}
	}
 
	return 0;
}

O último deles (Trilhas) tá meio problemático. Tá fazendo um monte de coisa que não precisava… :S É que deu uns problemas lá na hora e eu tava cansado por causa do Duende e daí tive lag pra interpretar o enunciado e já que o tempo tava acabando por causa de problemas com o computador onde tava fazendo a prova eu fiz de uma maneira bem precária! Acho que ele tá com erros…

O do Duende é o mais interessante. Os outros dois não tiveram muita graça. O Trilhas também era bem fácil, mas inesperadamente o meu cérebro deu um Segmentation Fault quando fui fazer ele.

Gostaria que se alguém achasse algum erro em algum dos scripts me avisasse. O pessoal da OBI ainda não divulgou um gabarito pra testar os programas e nem o resultado. Acredito que semana que vem deve sair alguma coisa…

2 comentários sobre “Solução dos Problemas da OBI2005

  1. ola,
    aqui, as suas soluçoes de problemas da obi são muito pouco comentadas…

    ficariam muito melhores e mais faceis de entender se voce comentasse os passos + importantes do programa…

    abraço

  2. O meu da trilha ficou assim:

    #include
    using namespace std;
    int main(){
    int qtd, r, p1, ant, subida, subida2, sentido_certo, menor, pos_menor = 1;
    cin >> qtd;
    for (int i = 0; i > r;
    for (int p = 0; p > p1;
    if (p > 0 )
    if (p1-ant > 0)
    subida += p1-ant;
    else
    subida2 += ant-p1;
    ant = p1;
    }
    if (subida < subida2)
    sentido_certo = subida;
    else
    sentido_certo = subida2;
    if (i == 0)
    menor = sentido_certo;
    if (sentido_certo < menor){
    menor = sentido_certo;
    pos_menor = i+1;
    }
    }
    cout << pos_menor << endl;
    return 0;
    }

Deixe uma resposta