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. :)

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

• Rede Salesiana de Escolas
• DomBosco.net
• Escol@24Horas.com.br
• Quadro de Mérito no site da OBI

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:

• ~`GINSAL~~
• Páginas Literárias

(links perdidos com o tempo)

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.

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…

Acabei de resolver o problema Palavras Cruzadas; até agora foi o mais difícil da OBI 1999 (ainda que fácil se comparado a problemas de outras OBIs mais recentes, como Rede Ótica e Orkut):

Na outra vez que eu tinha tentado fazer foi difícil, mas dessa vez foi tranquilo. Bom… O algoritmo tá bem simples e já coloquei na seção de scripts. Gostei do programa, a saída é bem bonita. :lol:

//Palavras Cruzadas - OBI1999

#include <stdio.h>
#define NMAX 102

int nu[NMAX][NMAX], proximonumero;
char mt[NMAX][NMAX];

int numera(i, j) {
	if (!nu[i][j]) {
		nu[i][j]=proximonumero++;
		//printf("É numerada a coordenada %d %d com %d.\n", i, j, nu[i][j]);
	}
}

int main() {
	int n, m, i, j, k, teste=1, vertical, horizontal;
	char enter;

	while (scanf("%d %d", &n, &m)&&n) {
		//imprime o número do teste
		printf("Teste %d\n", teste++);
		//zera as matrizes
		for (i=0; i<=n+1; i++) {
			for (j=0; j<=m+1; j++) {
				mt[i][j]='*';
				nu[i][j]=0;
			}
		}
		//pega o enter
		scanf("%c", &enter);
		//pega os chars e coloca na matriz
		for (i=1; i<=n; i++) {
			for (j=1; j<=m; j++) {
				scanf("%c", &mt[i][j]);
			}
			scanf("%c", &enter);
		}
		//define o proximo numero pra 1
		proximonumero=1;
		vertical=0;
		horizontal=0;
		//numera a matriz
		for (i=1; i<=n; i++) {
			for (j=1; j<=m; j++) {
				if (mt[i][j]!='*') {
					if (mt[i][j-1]=='*'&&mt[i][j+1]!='*') {
						numera(i, j);
						horizontal=1;
					}
					if (mt[i-1][j]=='*'&&mt[i+1][j]!='*') {
						numera(i, j);
						vertical=1;
					}
				}
			}
		}
		//imprime palavras horizontais
		if (horizontal) {
			printf("Horizontais:\n");
			for (i=1; i<=n; i++) {
				for (j=1; j<=m; j++) {
					if (mt[i][j]!='*'&&mt[i][j-1]=='*'&&mt[i][j+1]!='*') {
						printf("  %d. ", nu[i][j]);
						for (k=j; mt[i][k]!='*'; k++) {
						       printf("%c", mt[i][k]);
						}
				 		printf("\n");
					}
				}
			}
		}

		//imprime palavras verticais
		if (vertical) {
			printf("Verticais:\n");
			for (i=1; i<=n; i++) {
				for (j=1; j<=m; j++) {
					if (mt[i][j]!='*'&&mt[i-1][j]=='*'&&mt[i+1][j]!='*') {
					       printf("  %d. ", nu[i][j]);
					       for (k=i; mt[k][j]!='*'; k++) {
						       printf("%c", mt[k][j]);
					       }
					       printf("\n");
					}
				}
			}
		}

		//enter
		printf("\n");
	}
}

Estive utilizando o screen e Lynx, Tmsnc, etc. por um tempo. É muito bom, bastante leve. É uma ótima opção para computadores lentos ou pra quem não quer perder tempo abrindo modo gráfico (se bem que se for pra ir na internet, ainda vale mais a pena abrir um Fluxbox ou algo do tipo). Bom… Uma vantagem também é já usar Mutt e Tmsnc normalmente. Aliás, o TMSNC tá muito bom! Saiu essa semana o 0.2.0b com algumas novidades legais como sons de login, mensagens, etc.

Já passou uma semana de aula… É meio corrido e não dá muito tempo pra programar, mas acabo estudando TeX durante a aula para escrever os cadernos. O treino de vôlei vai começar esta semana e ainda não falei com o Vavá sobre o treino para as olimpíadas de matemática.

Consegui convencer dois amigos a usarem Firefox mostrando o meu post sobre o Fotolog.net e espero que este artigo da falha ajude a mostrar para as pessoas que o Internet Explorer é muito vulnerável. Já enviei também um e-mail ao administrador do Fotolog.net falando do bug.

No mais, nada…