Arquivo da tag: obi 2005

Resultado da Seletiva IOI

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.

Museu do Ipiranga 2

Hoje cheguei em Itajaí pela manhã depois de uma semana muito legal visitando pontos turísticos e participando de eventos de vários tipos em São Paulo (as fotos estão disponíveis no meu álbum do Flickr).

Perto da hora do almoço, o resultado da seletiva para a Olimpíada Internacional de Informática finalmente saiu. E me surpreendi com a pequena quantidade de pontos que fiz. Eu tinha feito as seis questões e esperava fazer uns 400 pontos (sabia que o problema do Caixeiro Viajante da primeira prova estava errado e considerava alguns errinhos), mas fiz apenas 180! :(

Só fiz 10 pontos no problema Campos de Minhoca e 40 no Criptologia, entre outras coisas inesperadas como o Floyd Warshall não ser suficiente para resolver o problema do Caixeiro Viajante da segunda prova, como eu pensava… E pior é que em todos os testes cai ao menos um caso que meu programa não cobre!

Mas a maior decepção foi mesmo no Criptologia. É um problema bem fácil de substituição de caracteres… Eu não fiz os 100 pontos possíveis por não imprimir um espaço no começo da frase caso tivesse. Acho que isso não tá certo, já que uma frase (mensagem) NUNCA começa com um espaço e meu programa está imprimindo tudo conforme solicitado, com exceção desse espaço. (E o Tchê disse na Tutoria que a falta de um espaço não deveria tirar pontos na olimpíada.) Por isso, enviei um e-mail solicitando recorreção e admissão disso. Pelo resultado atual, estou em nono lugar e com os 60 pontos desse problema eu fico em quinto. Já é uma diferença boa e acho bem mais legal ficar só a uma vaga de estar na internacional…

Editado – Quinto lugar

A coordenação da OBI aceitou meu pedido e agora estou em quinto lugar com 240 pontos! Ou seja, se alguém não puder ir por compromisso ou saúde, acho que sou eu que participo da equipe brasileira no lugar dele. :D Bem que podia ter mais uma coisinha assim com mais 50 pontos, né? :lol:

Agora tô começando a me preparar pro ano que vem.

Pretendo rever os slides do curso, ler o livro do Cormen, estudar mais matemática/geometria e resolver os problemas do USACO Training Gateway e da Universidade de Valadollid pra ver se consigo ir pro México ano que vem… Acho que tenho bastante chances (aliás, descobri que nesse ano eu já tinha, mas por errinhos não fui tão bem como pensei que tivesse ido).

O curso desse ano foi bem interessante, aprendi bastante e mesmo não indo tão bem na seletiva, agora estou animado pro ano que vem. :D

Semana Azul

Vou estender o tópico para fazer uma propaganda da Semana Azul. A Semana Azul é um evento on-line que ocorre entre 25 e 31 de julho de 2005. Para acessar as palestras que acontecem todos os dias da semana às 20h00, o participante precisa ter algum cliente de IRC e entrar na rede da Freenode (irc.freenode.net) no canal #mozilla-br. Irão ocorrer palestras legais sobre projetos que envolvem XUL e Mozilla… A programação completa está disponível aqui: http://www.mozilla.org.br/semanaazul/?n=SAr1.ProgramacaoIRC. :) Participem!

Curso de Programação Avançada na UNICAMP

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.

Hoje chega ao fim o Curso de Programação Avançada dos premiados na OBI2005 aqui na UNICAMP. Durante essa semana aprendi bastante e não tive tempo pra fóruns, e-mail e IMs. Então, se você foi um cara que “ficou no vácuo”, saiba que não foi uma coisa intencional. Mas vamos ao que interessa!

Achei muito legal o curso e vou ter coisas pra estudar até a OBI do ano que vem. Vou falar um pouco sobre a aula teórica de cada dia.

Complexidade (Prof. Ricardo Dahab)

Segunda-feira tivemos uma aula que abordou principalmente a complexidade de algoritmos. Entendi as classes e como calcular custos dos algoritmos, além de abordar algumas técnicas de backtracking e “divisão e conquista”. Durante a tarde, fizemos o problema “Ilha da Lógica”, do site da Universidade de Valadollid. Um problema simples, mas meio chato de implementar.

Grafos (Prof. David Sotelo)

Terça-feira tivemos uma aula sobre algoritmos em grafos, começando de definições básicas, algoritmos de busca e depois falando sobre alguns algoritmos como Prim e Dijkstra. Foi uma aula proveitosa a partir da metade… :) A tarde, resolvi o problema Graph Connectivity da UVA.

Programação Dinâmica (Prof. Cid C. de Souza)

Quarta-feira tivemos o que foi, na minha opinião, a melhor aula da semana. Com slides muito bem feitos, o prof. Cid conseguiu finalmente com que eu entendesse programação dinâmica e saí conhecendo algoritmos clássicos e entendendo o “esquema”. A tarde, resolvi o problema “Compromise” da UVA.

Geometria Computacional (Prof. Walter Mascarenhas)

Quinta-feira tivemos aula sobre geometria computacional. Achei complicado e não entendi nada… Depois tenho que estudar com mais calma em casa.

Grafos Avançados (Prof. Cláudio Luquesi)

Hoje tive uma aula bem legal sobre fluxos em rede em que eu aprendi o algoritmo básico e várias variações. Foi uma excelente aula.

Seletiva IOI

Ontem fiz a primeira parte da prova seletiva para a Olimpíada Internacional de Informática. Ela tinha três problemas, resolvi os três, mas para nenhum deles fiz o melhor tempo. Amanhã será feita a segunda parte e depois que sair o resultado, eu comento sobre os problemas e como resolvi.

Acho que tenho alguma chance, mas… nunca se sabe. Tudo depende de amanhã. Eu fui bem na prova de ontem e acho que se ir assim amanhã talvez consiga uma vaga na Polônia. :D

Solução dos Problemas

Resolvi vários problemas aqui e marquei vários outros para resolver. Assim que eu chegar em casa, eu posto eles no site (alguns eu já postei) e comento mais.

Resto das Férias

Amanhã, depois da Seletiva, o curso acaba e devo ir pra São Paulo amanhã mesmo ou domingo. Ficarei lá uma semana com meu irmão Bruno curtindo shows e visitando minha tia e meu primo.

Observações

A gente tá tendo aula prática em outro lugar, não no Instituto de Computação onde foi ano passado. Lá era bem melhor e tinha coisas como Mutt pra facilitar a vida. Aqui sempre que a gente dá logout é tudo deletado na nossa home e isso torna tudo muito chato. Então tô trabalhando só em SSH pro IC da Unicamp (todos têm uma senha lá também) ou pro meu site mesmo. :)

Ah, e São Paulo é tri-campeão da Libertadores! 4×0!

E mais uma coisa que eu tinha esquecido, e também aprendi aqui com um monitor: o scanf aceita ERs no primeiro argumento. :) Isso é baita útil…

Simplificando…

Aqui tá bem legal, mas não tô com tempo pra detalhar nada. :D Então, até mais. :)

Primeiro Lugar na OBI 2005!

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.

Quadro de Mérito OBI2005 Programação Nível 1

Esse post é uma edição do 395 pontos!

Utilizando uns programas Bash que eu fiz, acho que fui o primeiro a ver meu resultado da Olimpíada Brasileira de Informática 2005, seguindo links do Mapa do Conteúdo que foram aparecendo em alguns momentos da tarde do dia 06/06 (e, misteriosamente, sumindo logo após). Para minha surpresa, fiz 395 dos 400 pontos possíveis!

Só errei um teste na prova (o teste 3 da questão Trilhas), o que me garantiu a única medalha de ouro da Programação Nível 1 e primeiro lugar isolado.

O segundo lugar, de Fortaleza, fez 300 pontos.

Agora vou pra UNICAMP em julho fazer o curso de programação avançada (com tópicos muito legais, que vão acabar com muitas dúvidas minhas – como Programação Dinâmica e Algoritmos Gulosos) disputar uma vaga na IOI na Polônia. Acho difícil conseguir vencer, até porque cinco pessoas gabaritaram a Programação Nível 2 (ou seis?), mas vou me esforçar para chegar o mais perto possível das quatro vagas.

Programas em Bash usados para ver o resultado antes do normal

Primeiro Programa

#!/bin/bash
 
musica="/ntfs/Program Files/MSN Messenger/type.wav"
endereco="http://olimpiada.ic.unicamp.br"
 
mv ~/.obi ~/.obi-o > /dev/null 2> /dev/null
lynx -source "$endereco" > ~/.obi
 
if [ "`cat ~/.obi`" = "`cat ~/.obi-o`" ]; then
       echo "34m1mO site da OBI não foi atualizado desde a última vez que o programa foi executado.�m"
else
       echo "31m1mO site da OBI foi atualizado desde a última vez que o programa foi executado!�m"
       play "$musica"
       firefox "$endereco"
fi

Este programa verifica quando o site é atualizado. Quando a música tocou, o navegador se abriu e vi que apareceu um novo link (Copy of …)

Segundo Programa

#!/bin/bash
action=""
logurl=""
 
echo "compet_type=3&school_name=&school_city=&school_state=choose&compet_name=&order=compet_id&batch_size=10000&show=Consulta" | lynx -source -post-data "$action" > .t
 
grep "MostraLog" .t > .t2 #sim, eu sei que não precisava de tantos arquivos
 
sed -e 's/<a href="MostraLog?id=(.*)">.*</a>/1/' .t2 > .t3 #tá, eu sei que eu devia ter usado [0-9]+ mas não é necessário
 
for i in `cat .t3`; do
       printf "34m1mVerificando id $i...�m"
       lynx -dump "$logurl?id=$i" | grep "Total de pontos" > .t4
       pontuacao=`sed -e 's/Total de pontos:  (.*)/1/' .t4`
       echo "$pontuacao"
        # uma coisa que eu devia ter feito aqui é pegar o nome do cara (.t2 | grep $i | sed...)
       if [ -n "$pontuacao" ]; then
              if [ $pontuacao -ge 200 ]; then
                     echo "$i|$pontuacao" >> .ponto #isso aqui é só pra eu ver quem é certinho
              fi
       fi
done

Este foi bastante modificado depois e fiz várias versões melhores dele para pegar várias vezes o resultado. Mas esse serve para mostrar a idéia do negócio… ;)

Essa conquista em outros sites

Estatísticas, Programação Dinâmica, OBI Programação Nível 2

ATENÇÃO: Este conteúdo foi publicado há 13 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.

Em primeiro lugar, quero dar a notícia de que as visitas do site só tem crescido. Nesse mês, o site tem recebido 100 ips únicos por dia e uns 500 hits. Para um pequeno blog, são estatísticas boas. As palavras-chave mais procuradas e a posição do meu site na procura por ela no Google (somente em português) são:

  • tableless – sétima posição
  • qemu – décima-primeira posição
  • problemas lógicos – quarta posição
  • dobradura – décima-sexta posição
  • gráfico de setores – décima-oitava posição
  • permutação – sexta posição
  • obi2005 – nona posição E “obi 2005” – terceira posição
  • biografia de linus torvalds – sexta posição emoticon

Ainda tem outras procuras interessantes e outras nada a ver, mas essas são as mais procuradas. É incrível como as pessoas clicam na minha biografia quando procuram pela biografia do criador do Linux! :blink: Acho legal as pessoas acharem meu site procurando por tableless, problemas lógicos, algoritmos, OBI2005 e nomes de problemas lógicos que eu fiz (também tem muita gente que procura por MMC e MDC).

Quanto a navegadores, o IE6 ainda tá dominando tudo. É uma pena que o pessoal use esse navegador pra entrar no meu site cujo um dos principais objetivos é apresentar os padrões web, tableless e faço de tudo pra acabar com o monopólio desse péssimo navegador e incentivar o software livre.

Por causa dos trabalhos, tenho programado muito em PHP, feito muitos designs no Fireworks (tô tendo que rebootar direto, porque desenho lá e depois venho pro Linux programar) e escrito XHTML/CSS. Alterei um pouco o programa ouvir (agora versão 1.1!). Ele já tá bem mais legalzinho do que aquela primeira versão que eu tinha postado e depois eu posto ele aqui.

Hmmm… Estive procurando umas coisas no livro vermelho (Algoritmos: Teoria e Prática) e descobri duas coisas desse livro.

  1. Ele tem tudo. É um livro completo, procura qualquer coisa de algoritmos ali que se acha tudo.
  2. É ilegível. :blink:

É muito complicado entender as coisas contidas nele, então tenho estudado um pouco por materiais na internet mais simples e só depois que peguei mesmo a coisa que leio no livro. Mas mesmo assim, bóio um pouco quanto a custos.

Por causa do problema Mochila (Pedido de Desculpas da OBI2005), acabei tentando aprender alguma coisa sobre programação dinâmica, mas não tô entendendo NADA! Só entendi o conceito e pra que serve, mas como fazer não sei. Não entendo como fazer as recorrências (e daí de repente, abro o índice do livro vermelho e acho lá um capítulo só sobre como fazer recorrências! – mas não entendo nada… :( )

Mas os outros problemas da OBI2005 Programação Nível 2 estão todos resolvidos! São bem fáceis. O único problema difícil do nível 2 da programação era esse de programação dinâmica mesmo… Publiquei eles na seção de scripts e vou fazer um pequeno comentário sobre cada um deles. Ah… E já que eu não peguei a prova de verdade (o Paulo Victor me passou um resumo dos problemas), não coloquei limites e saídas corretos.

Bafo

Um programa ridículo, igual o Cofrinhos da Vó Vitória (que foi o primeiro programa da OBI que eu fiz, quando tava começando a aprender C).

Solução:

//Bafo - OBI2005
#include <stdio.h>
 
int main() {
	int n, j1, j2, t1=0, t2=0, i, teste=1;
 
	while (scanf("%d", &n)&&n) {
		printf("Teste %d\n", teste++);
		t1=0;
		t2=0;
		for (i=1; i<=n; i++) {
			scanf("%d %d", &j1, &j2);
			t1+=j1;
			t2+=j2;
		}
		if (t1>t2) {
			printf("Aldo");
		} else {
			printf("Beto");
		}
		printf("\n\n");
	}
	return 0;
}

Transmissão de Energia

Um programa de grafos que busca ver se o grafo é conexo ou não. Uma simples busca de profundidade resolve.

Solução:

//Transmissão de Energia - OBI2005
#include <stdio.h>
#define NMAX 101
 
int g[NMAX][NMAX], achou[NMAX], n, achados;
 
void acha(int x) {
	int i;
 
	achou[x]=1;
	achados++;
	for (i=1; i<=n; i++) {
		if (g[x][i]&&!achou[i]) {
			g[x][i]=0;
			g[i][x]=0;
			acha(i);
		}
	}
}
 
int main() {
	int e, i, j, x, y, teste=1;
 
	while (scanf("%d %d", &n, &e)&&n) {
		achados=0;
		for (i=1; i<=n; i++) {
			achou[i]=0;
			for (j=1; j<=n; j++) {
				g[i][j]=0;
			}
		}
 
		for (i=1; i<=e; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]=1;
			g[y][x]=1;
		}
 
		acha(1);
 
		printf("Teste %d\n", teste++);
		if (achados==n) {
			printf("normal");
		} else {
			printf("falha");
		}
		printf("\n\n");
	}
 
	return 0;
}

Vivo ou Morto

Um jogo de Vivo ou Morto bem fácil de fazer mas difícil de explicar.

Solução:

//Vivo ou Morto - OBI2005
#include <stdio.h>
//Não sei qual o número máximo de jogadores!
#define NMAX 101
 
int main() {
	int jogador[NMAX], njogadores, nrodadas, i, j, k, vivos, ordem, fez;
 
	scanf("%d %d", &njogadores, &nrodadas);
	for (i=1; i<=njogadores; i++) {
		scanf("%d", &jogador[i]);
	}
	for (i=1; i<=nrodadas; i++) {
		scanf("%d %d", &vivos, &ordem);
		for (j=1; j<=vivos; j++) {
			scanf("%d", &fez);
			if (fez!=ordem) {
				jogador[j]=0;
			}
		}
		for (j=1; j<=vivos; j++) {
			if (!jogador[j]) {
				for (k=j; k<vivos; k++) {
					jogador[k]=jogador[k+1];
				}
			}
		}
	}
	printf("%d\n", jogador[1]);
}

Mini-poker

Um jogo chato… :lol: Uma baita falta de criatividade. Um programa não-lógico onde são dadas cinco cartas e eu devo determinar a pontuação do cara…

Solução:

//Mini-poker - OBI2005
#include <stdio.h>
 
int pontuacao(int c[]) {
	//Regra I
	if (c[1]==c[2]-1&&c[2]==c[3]-1&&c[3]==c[4]-1&&c[4]==c[5]-1) {
		return 200+c[1];
	}
 
	//Regra II
	if (c[1]==c[4]||c[2]==c[5]) {
		return 180+c[2];
	}
 
	//Regra III
	if ((c[1]==c[3]&&c[4]==c[5])||(c[3]==c[5]&&c[1]==c[2])) {
		return 160+c[3];
	}
 
	//Regra IV
	if (c[1]==c[3]||c[2]==c[4]||c[3]==c[5]) {
		return 140+c[3];
	}
 
	//Regra V
	if ((c[1]==c[2]&&c[4]==c[5])) {
		if (c[1]>c[4]) {
			return 3*c[1]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[1]+20;
		}
	}
	if ((c[1]==c[2]&&c[3]==c[4])) {
		if (c[1]>c[3]) {
			return 3*c[1]+2*c[3]+20;
		} else {
			return 3*c[3]+2*c[1]+20;
		}
	}
	if ((c[2]==c[3]&&c[4]==c[5])) {
		if (c[2]>c[4]) {
			return 3*c[2]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[2]+20;
		}
	}
 
	//Regra VI
	if (c[1]==c[2]||c[2]==c[3]) {
		return c[2];
	}
	if (c[3]==c[4]||c[4]==c[5]) {
		return c[4];
	}
 
	//Regra VII
	return 0;
}
 
int main() {
	int n, teste, c[6], carta, i, j;
 
	scanf("%d", &n);
	for (teste=1; teste<=n; teste++) {
		//Pega os valores e faz um Insertion Sort
		for (i=1; i<=5; i++) {
			scanf("%d", &carta);
			for (j=i-1; j>0&&c[j]>carta; j--) {
				c[j+1]=c[j];
			}
			c[j+1]=carta;
		}
 
		printf("Teste %d\n%d\n\n", teste, pontuacao(c));
	}
 
	return 0;
}

Saiu o gabarito da iniciação… Meu irmão, Lucas, acertou 14 no nível de quintas e sextas séries (ele tá na quinta) e ganhou Menção Honrosa. E o nosso, não vai sair não?

Projetos do Salesiano, SED/Bash, Programação Nível 2

ATENÇÃO: Este conteúdo foi publicado há 13 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.

Em primeiro lugar, publiquei dois projetos do colégio (dentro dos padrões web, um que não funciona direito no IE) sexta-feira. O pessoal tava reclamando que a página tava desatualizada e tinha gente procurando por “ginsal 2005” no Google e chegando aqui, então estou postando os links para o projeto Ginsal 2005 e Páginas Literárias aqui mesmo:

Eles não foram publicados antes porque tô com bastante coisa pra fazer lá no colégio, entre essas um site totalmente novo.

E mesmo que você não seja do colégio, dá uma olhada nos códigos totalmente dentro dos padrões nos dois sites. O Páginas Literárias usa até tags q e cite na página inicial! Legal também o rodapé que eu coloquei nos dois projetos, sugerindo “qualquer navegador”, sem ser IE.

Em segundo lugar, obrigado ao Paulo Victor Eufrásio, de Fortaleza, que me mandou uma síntese dos problemas da OBI2005 Programação Nível 2! Já fiz alguns e depois publicarei tudo junto. O nível não tá muito alto, mas achei difícil aquele problema Mochila (o povo que foi na Programação pra UNICAMP ano passado já sabia a solução, mas eu não!).

E finalizando, hoje dei meus primeiros passos no sed. Eu tava achando uma vergonha ter que passar pelo aplicativo php e usar ereg_replace nos meus programas Bash e adorei o sed! Criei um programinha bem legal para ouvir músicas. Postei os screenshots no Flickr e o código aqui embaixo.

#!/bin/bash
toca() {
       echo "^[[31m^[[1m$1"'a. ocorrência^[[0m'
       musica="`head -$1 ~/.tmp-musica | tail -1`"
       nome="`echo $musica | sed -e 's/(.*)/(.*)/([0-9]*) (.*).mp3/4/'`"
       autor="`echo $musica | sed -e 's/(.*)/(.*)/([0-9]*) (.*).mp3/1/'`"
       album="`echo $musica | sed -e 's/(.*)/(.*)/([0-9]*) (.*).mp3/2/'`"
       echo "Nome:    ^[[33m^[[1m$nome^[[0m"
       echo "Autor:   ^[[33m^[[1m$autor^[[0m"
       echo "Álbum:   ^[[33m^[[1m$album^[[0m"
       echo "Caminho: ^[[33m^[[1m$musica^[[0m"
       play "$path/$musica"
       echo ""
}
path="/mnt/ntfs/Documents and Settings/Tiago Madeira/My Documents/My Music"
echo "^[[36m^[[1mouvir 1.0 (c)^[[0m"
echo "^[[1mpor Tiago Madeira (contato em tiagomadeira.net^[[0m"
echo ""
echo "^[[1mEntrando no diretório das músicas...^[[0m"
cd "$path"
echo "^[[1mProcurando palavras-chave...^[[0m"
tree -f * | grep -i "$1.*.mp3" > ~/.tmp-musica
 
echo "^[[1mFormatando a(s) palavra(s)-chave...^[[0m"
sed -e 's/^[| -]*//' ~/.tmp-musica > ~/.tmp-music
 
mv ~/.tmp-music ~/.tmp-musica
echo "^[[1mContando número de ocorrências encontradas...^[[0m"
wc -l ~/.tmp-musica > ~/.wc-tmp-musica
echo "^[[1mFormatando número de ocorrências encontradas...^[[0m"
num=`sed -e 's/([0-9]*) (.*)/1/' ~/.wc-tmp-musica`
 
echo ""
 
echo "^[[34m^[[1mFoi(ram) encontrada(s) $num ocorrência(s):^[[0m"
cat -n ~/.tmp-musica | sed -e 's/^[[:blank:]]*([0-9]*)[[:blank:]]*(.*)/1: 2/'
 
echo ""
 
echo "^[[31m^[[1mDigite o número da música que você deseja ouvir,"
echo "ou 't' para tocar todas ou 's' para sair.^[[0m"
echo ""
 
while :; do
 printf "^[[31m^[[1m#: ^[[0m"
 read d
 case $d in
  's'|'S')
   break
   ;;
  't'|'T')
   i=1
   while [ "$i" -le "$num" ]; do
    toca $i
    i=`funcoeszz zzcalcula $i+1`
   done
   ;;
  *)
   toca $d
   ;;
 esac
done
 
rm ~/.tmp-nome > /dev/null
rm ~/.tmp-musica 2> /dev/null
 
echo "^[[1mAté a próxima!^[[0m"

Agora já modifiquei bastante esse programa e ele tá na minha seção Portifólio, mas essa aí foi a primeira versão.

Eu nunca tinha feito nada tão evoluído no Bash e agora tô até começando a me achar um programador bash. Incrível como é legal desenvolver nele! :)

No mais, não aconteceu nada de novo. Só tô decepcionado por ter errado um problema da OBI, cheio de trabalhos de escola mas desenvolvendo bastante coisa legal aqui agora que meus sistemas estão ficando estáveis.

Solução dos Problemas da OBI2005

ATENÇÃO: Este conteúdo foi publicado há 13 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…