Estou hospedado na casa do meu irmão, em Campinas, desde ontem de manhã (viajei domingo a noite de ônibus). Hoje foi o primeiro dia do curso preparatório para a seletiva da IOI2006, que começou às 9h00 devagarinho.

O dia hoje serviu para “nivelar” os participantes e treinar um pouquinho a resolução de problemas. De manhã, algumas pessoas tiveram uma aula sobre estruturas de dados, grafos e o básico de programação dinâmica e outras (a maioria) resolveram três problemas da Universidade de Valladollid:

412 – Pi

Enunciado – Minha Solução

Não é um problema muito complexo, mas eu usava um algoritmo muito demorado para determinar se dois números tinham ou não um fator comum, que não passava por tempo limite excedido. Então, o Fábio Dias Moreira nos passou uma propriedade bem interessante de MDC (Máximo Divisor Comum):

mdc(x, y) = mdc(x%y, y)

(onde o % é o resto da divisão, no C)

Aí dá pra fazer uma função recursiva mdc bem rápida, que eu apliquei na [minha solução][3].

441 – Lotto

Enunciado – Minha Solução

Esse problema nem tem muito o que comentar. Implementação de dois minutos… hehehe… Eu podia ter feito uma função recursiva pra ficar um pouco mais “decente” (e poder mudar de 6 para outro número no futuro), mas não tinha necessidade, então ficou assim mesmo (e passou de primeira no site).

543 – Goldbach’s Conjecture

Enunciado – Minha Solução

O objetivo é provar a Conjectura de Goldbach para todos os pares menores que 1000000. Meu programa ainda não roda dentro do tempo, mas depois vou continuar a adapta-lo. Eu posso, por exemplo, ir fazendo a média entre o maior possível e o menor possível (aquele “algoritmo” que usamos quando alguém fala: “Pensei num número de 1 a 100. Tente advinhar…”) ao invés desses loops, o que já vai tornar o programa mais rápido (não sei se o suficiente).

Nesse problema, o Fábio me lembrou do Crivo de Eratóstenes. Bem interessante, nunca tinha implementado. :)

Provavelmente pela primeira vez, o almoço dos participantes do curso não foi no “bandeijão”, mas sim num restaurante chique perto do IC. Achei bem legal… Além de andar menos, o ambiente é melhor e a comida também.

Durante a tarde, o Fábio nos passou o algoritmo de Longest Common Subsequence (esse eu já sabia… hehehe) e depois o algoritmo que resolve o problema Subseqüências que caiu na prova da segunda fase (esse um pouquinho mais complicado!). Esse segundo eu pretendo implementar e depois até fazer um artigo sobre…

Depois, o Fábio nos deu algumas dicas, principalmente sobre os cálculos problemáticos que o computador faz com pontos flutuantes (algo bem interessante, que eu não entendia porque acontecia). Por exemplo, quando criamos um double x=0.1 o seu valor não é 0.1, mas sim o 1/1010 (em binário) que dá uma dízima periódica! E isso não é muito agradável, pode gerar até loops infinitos… Então, ele sugeriu que criássemos uma função para comparar dois números reais, com um código como esse:

/*
USO: Substituir...
x == y <==> cmp(x, y) == 0
x != y <==> cmp(x, y) != 0
x < y <==> cmp(x, y) < 0
x ### y <==> cmp(x, y) ### y

O "###" é "qualquer-coisa". Hehehe...
*/

#include <math.h>

const double EPS = 1.0e-10

int cmp(double x, double y) {
	if (fabs(x-y)<EPS) {
		return 0;
	} else if (x>y) {
		return 1;
	} else {
		return -1;
	}
}

Foi um bom ponto de partida legal, começamos de leve. Ainda não sei sobre o quê será a aula de amanhã…

Seletiva IOI

Neste ano vão haver quatro provas para selecionar os quatro participantes que irão representar o Brasil na Olimpíada Internacional de Informática em agosto, no México. As três primeiras, identificadas como “testes” no calendário da seletiva, terão apenas um problema e durarão duas horas cada uma. A última será no domingo, às 7h45min, terá três questões e durará cinco horas (pô, vou perder o comecinho do jogo de Brasil contra Austrália!). Achei legal esse método, mas como o César Kawakami disse: dessa maneira, não treinamos a estratégia, que é algo importante para a prova da IOI.

Por enquanto é só. Se der tempo, pretendo colocar um post por dia sobre o curso até o final dessa semana. :)

Em primeiro lugar, venho por meio deste post comunicar que não uso mais MSN Messenger. O mensageiro instantâneo da Microsoft saiu da minha lista de contas do CenterICQ para a entrada de dois novos e melhores: IRC e GoogleTalk/Jabber. Cheguei a conclusão de que quem quer falar comigo deve usar o que eu uso e não ao contrário, por um motivo óbvio: o meu é melhor que o deles.

Esta decisão fez com que eu perdesse centenas de contatos, mas acho que foi a decisão certa a ser tomada. Quem quiser me contatar agora, pode me adicionar no ICQ como 147330555, GoogleTalk como tmadeira em gmail.com e no IRC/Freenode, como tiagomadeira.

O segundo ponto importante deste post é o anúncio da OBM, Segunda Fase. A prova acontecerá no sábado que vem, dia 03 de setembro. Acho difícil eu conseguir medalha nesse ano (Terceira Fase é difícil!), mas vou tentar me esforçar o máximo possível… Esta semana tivemos o treino para olimpíadas com o Vavá, aprendi algumas coisas úteis. E ontem conversei com o César Kawakami no ICQ que me deu umas dicas interessantes também sobre Teoria dos Números. Vou tentar aprender alguma coisa sobre isso nos próximos dias…

As aulas de matemática dessa semana foram pouco produtivas porque eu andei faltando algumas para a divulgação do fórum do colégio. Então, só deu pra fazer dois problemas: a implementação da Máxima Subcadeia Comum (LCS/Programação Dinâmica):

//LCS - Longest Common Subsequence
//Programação Dinâmica - MSC - Maior Subcadeia Comum

#include <stdio.h>
#define SMAX 1001
#define DIAGONAL 1
#define LADO 2
#define CIMA 3


//n = tamanho de x
//m = tamanho de y

int c[SMAX][SMAX], b[SMAX][SMAX], n, m;
char x[SMAX], y[SMAX];

int lcs_recupera(int i, int j) {
	if (i==0||j==0) {
		return 0;
	}
	if (b[i][j]==DIAGONAL) {
		lcs_recupera(i-1, j-1);
		printf("%c", x[i]);
	} else if (b[i][j]==CIMA) {
		lcs_recupera(i-1, j);
	} else {
		lcs_recupera(i, j-1);
	}
}

int main() {
	int i, j;


	printf("LCS - Longest Common Subsequence\nPor Tiago Madeira\n\n");
	printf("Digite o tamanho da string X: ");
	scanf("%d", &m);
	printf("Digite o tamanho da string Y: ");
	scanf("%d", &n);

	scanf("%*c");
	printf("Digite a string X: ");
	for (i=1; i<=m; i++) {
		scanf("%c", &x[i]);
		c[i][0]=0;
	}
	scanf("%*c");
	printf("Digite a string Y: ");
	for (i=1; i<=n; i++) {
		scanf("%c", &y[i]);
		c[0][i]=0;
	}

	printf("\nPrograma raciocinando...\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			if (x[i]==y[j]) {
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=DIAGONAL;
			} else {
				if (c[i][j-1]>c[i-1][j]) {
					c[i][j]=c[i][j-1];
					b[i][j]=LADO;
				} else {
					c[i][j]=c[i-1][j];
					b[i][j]=CIMA;
				}
			}
		}
	}

/*	printf("\nMATRIX C\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", c[i][j]);
		}
		printf("\n");
	}

	printf("\nMATRIX B\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", b[i][j]);
		}
		printf("\n");
	}
*/

	lcs_recupera(m, n);
	printf("\n");
}

e um programa bem ridículo para calcular os termos e a soma de uma PA (é o que o prof. tá ensinando, aí achei bom pra fazer os exercícios mais rápido…):

//Aplicar as fórmulas das PAs

//Progressão Aritmética
//Programa desenvolvido por Tiago Madeira (c) 2005.

#include <stdio.h>
#define MAX 1000001

long double a[MAX], s[MAX];

int main() {
	long double r;
	int n;

	printf("Primeiro termo da PA: ");
	scanf("%Lf", &a[1]);
	printf("Razão da PA: ");
	scanf("%Lf", &r);

	//Eu podia fazer só pros que vão ser usados, mas não sei porquê, deu vontade de fazer assim... =)
	printf("\nAguarde o problema raciocinar tudo que ele tem para raciocinar...\n");
	for (n=2; n<MAX; n++) {
		a[n]=a[1]+r*(n-1);
		s[n]=(a[1]+a[n])*n/2;
	}

	printf("\nE agora, digite números para o programa dizer A e S dele.\n");
	do {
		printf("Número: ");
		scanf("%d", &n);
		if (!n) {
			break;
		}
		printf("Número na posição N = %.Lf\nSoma de 1 a N = %.Lf\n\n", a[n], s[n]);
	} while (n);

}

No começo do mês que vem é o Festival de Música de Itajaí. Acho que vou fazer oficina de Piano Popular avançado com o Prof. Michel Freidenson, que foi quem me deu aulas numa oficina semelhante há dois anos. A semana da música vai contar também com uns shows bem legais e o site oficial é este aqui.