Para não citar os fatos inúteis da escola (que são maioria), resolvi elogiar as aulas de história deste terceiro bimestre escrevendo neste artigo principalmente sobre filosofia. (e dessa vez não é só a do software livre!)

Nesse ano, voltamos a ter aulas de história de verdade, com uma professora de verdade e conteúdo de verdade. Quem conheceu o antigo professor Roberto, sabe do que eu estou falando… ;) Bom… Desde o começo do ano, estou gostando bastante de história. É uma matéria bem interessante que sempre nos faz pensar bastante e usar a lógica (aliás, a lógica lembra a razão, a Aristóteles e aos filósofos gregos). Não tá dando pra usar muito a lógica nas aulas de matemática, pois o professor se limita a ensinar PA, PG, funções de segundo grau e essas babaquices apenas usando fórmulas prontas. Sei que não é sua culpa, existe gente com sérias dificuldades de entendimento, mas acho que a escola muitas vezes é um repetir de fórmulas e exercícios que não ajudam a desenvolver o raciocínio. Então eu acho incrível que neste sentido, as aulas de história estão sendo as melhores deste ano.

Nesse bimestre, a professora Fabiana nos passou um trabalho sobre os filósofos gregos. O meu grupo falou sobre o filósofo Pitágoras, aquele que via números em tudo (e, sim, aquele mesmo que criou o Teorema) e aí comecei a ver uma relação (um pouco estranha) entre a matemática, a lógica, a razão, a filosofia e a história. E já que filosofia é amar a sabedoria, fica mais fácil entender toda essa relação, porque sabedoria é matemática… :D

Bom… Agora estou relendo “O Mundo de Sofia”, desta vez lendo e relendo com atenção até as cartas de dezenas de páginas às vezes um pouco complicadas sobre a história de vários filósofos. E fica aí a sugestão desse excelente livro (é interessante as histórias que o autor conta, que deixam coisas complicadas bem mais simples, como entender a filosofia de Demócrito como o brinquedo Lego).

Ahnnn… E acho que esse post foi só pra falar disso mesmo, só para não concluir nada, mas só dizer como vai a escola e que ainda tem alguma coisa para se aprender lá, uma coisa pra fazer pensar lá. :) E, aliás, ainda não tô concluindo nada, só tô vendo as idéias dos filósofos “famosos” e refletindo sobre elas…

Agora em História, continuamos estudando a Grécia, e agora partindo para os etruscos para chegar em Roma, mas fica registrada aqui a minha felicidade por estar tendo a oportunidade de pensar (usando o raciocínio lógico) mesmo nesta disciplina.

Agora mudando radicalmente de assunto para dizer as últimas novidades, além da filosofia…

O beta do Firefox 1.5 saiu, já estou utilizando-o como padrão… Achei ele igual o meu outro Deerpark Alpha (a.k.a. Firefox 1.6a1) Já que no outro post já comentei sobre suas vantagens, pararei por aqui.

A segunda fase da Olimpíada Regional de Matemática (catarinense) acontecerá no dia 24 deste mês e ainda não aprendi nada de novo sem ser filosofia, desde meu péssimo resultado na segunda fase da OBM.

A política no Brasil tá triste, não vejo escolhas sem mudar o sistema político, acabar com o capitalismo e com essa história de querer lucrar em tudo. Mas já que eu também sou um capitalista e nunca estudei direito sobre isso, e já tenho problemas menores suficientes para me incomodar, fica registrada aqui a tristeza mas o conformismo com essa situação. Na realidade, não sei quem não sabia ainda que os políticos brasileiros eram corruptos, mas agora é uma crise mais séria, tá tudo estourando… Não sei o que podemos fazer pra ajudar!

Fiz grandes alterações no meu site… Mudei a organização de todos os links, as regras do módulo ReWrite, adicionei feed do Flickr e criei um sitemap em XML do Google, mudei os permalinks dos artigos, as cores dos comentários, adicionei referências (permalinks) aos comentários… Um monte de coisa! :blink: E ainda tô querendo mexer em outras coisas… ;)

Tô testando uns sistemas de wiki para meu projeto de software livre para leigos, não tô conseguindo achar nada muito legal em PHP. Aquele “PHPWiki” não funciona direito, tive que modificar um monte de coisas e ainda assim apresentou problemas e tô quase decidindo fazer um eu mesmo.

Depois de um muito tempo, joguei RPG novamente este sábado… É meio esquisito interpretar um personagem na Idade Média, já é tão esquisito interpretar nós mesmos! :blink:

O site do Colégio tá quase pronto, estou precisando da biblioteca GD para trabalhar com redimensionamento de imagens e outras coisas com imagens no PHP e o cara que cuida do servidor FreeBSD ficou de instalar para mim, mas ainda não o fez… (gostaria tanto que fosse um Linux que eu mesmo tivesse configurado!)

Estou tentando fazer um Linux simples e acessível para minha família usar no computador que compartilha internet com o meu laptop, mas ainda não consegui nem instalar Linux (eu vivo instalando e desinstalando Linux aqui do lado… Esses caras não entendem como Linux é bom, a filosofia é linda e devemos parar de usar MSN e programas da Microsoft!). A mesma coisa eu quero fazer no Colégio depois que acabar de fazer o site. O Laboratório de Informática deveria ser só Linux. O KDE tem programas educativos tão legais, fora outros que podemos achar na internet… E tem programas para Ensino Médio que o nosso Lab. nem tem nem semelhantes. O problema é que ele tem uma grande quantidade de programas para a pré-escola e acho difícil encontrar bons clones para Linux. Eu acho que instalar Linux na escola é uma coisa indispensável e não pretendo sair de lá antes que esta missão esteja cumprida. Quero fazer ainda um esquema bem legal com um servidor e clientes usando NFS/NIS e com os clientes loggando no servidor e facilitando a vida da profa. de informática.

Fiz uma alteração nas Funções ZZ adicionando uma senha ao zzss (proteção de tela para console). O patch está disponível aqui no meu servidor: patch.zz (esse patch foi perdido pelo tempo) e para patchar basta usar patch -p1 apontando para ele o arquivo do patch (patch.zz) e colocar no File to patch a localização do seu arquivo funcoeszz (tem que ser a última versão).

Para finalizar, não tenho produzido muitos códigos / solucionado problemas lógicos, mas tenho pensado bastante logicamente e até ando vendo alguns grafos no pensamento e criando quase inconscientemente uns algoritmos… Embora não esteja implementando ou escrevendo os algoritmos, acho que estou desenvolvendo-os… Hehehe… (parece que eu sou louco, né?)

Coloquei várias imagens aí em cima pro post não ficar muito sem graça, já que ficou um pouco grande… A maioria delas não é tão importante, mas são boas pra saber em que pedaço do texto estamos… :)

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.

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

Fiquei um bom tempo sem fazer o treinamento da USACO, porque há algum tempo tinha parado no programa Prime Palindromes, cujo objetivo é listar todos os palíndromos primos entre dois números (limites: 5, 10.000.000).

Esta demora aconteceu porque eu, além de ter ficado muito tempo sem entrar na USACO e já ter me esquecido do problema, estava testando todos os números, vendo se eles eram palíndromos, depois primos e então imprimia. Quando eu entrei na USACO essa semana (idéia do César Kawakami, que também vai pra UNICAMP mês que vem e foi um cara que também me ajudou nesse problema) vi que tinham Hints que eu nunca tinha visto antes. E elas diziam que eu devia gerar palíndromos. Com isso ficou fácil…

Eu ainda boiei um pouco, porque só depois eu descobri uma coisa lógica e muito simples (que eu nunca tinha pensado antes): Para descobrir se um número N qualquer é primo, basta ver se ele é divisível pelos primos (no caso, eu usei todos os números, não só primos) de 2 a raiz de N. Bom, isso é bem óbvio… Mas ninguém nunca tinha me dito e eu nunca tinha visto em lugar nenhum! Então tive que pensar (descobrir sozinho mesmo).

Por preguiça de só fazer alguns for caso o mínimo fosse menor que X e maior que Y, meu programa, para qualquer caso, pega todos os palíndromos primos de 5 a 10000000! :blink: Eu não sabia se o tempo disso ia ser suficiente, então resolvi testar assim antes de fazer esses ifs antes do for e deu certo! Logo, nem precisa mais de nada… O tempo do meu programa para qualquer teste, no meu Linux, é 0,032 segundos. Na USACO apareceu como 0,05 segundos.

Código-fonte

//Prime Palindromes - USACO Training Gateway
//Tiago Madeira (c)

//Agora eu sei que dá pra fazer com custo bem menor,
//mas esse aí rolou na boa com 0.05 segundos.

/*
ID: contato1
PROG: pprime
LANG: C
*/

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

int eh_primo(long int num) {
	int i;

	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}

	return 1;
}

int main() {
	int i, j, k, l, cont=0;
	long int numero, min, max, v[10000];

	FILE *in=fopen("pprime.in", "r");
	FILE *out=fopen("pprime.out", "w");
	fscanf(in, "%d %d", &min, &max);
	fclose(in);

	v[cont++]=5;
	v[cont++]=7;
	for (i=1; i<=9; i+=2) {
		numero=i*10+i;
		if (eh_primo(numero)) {
			v[cont++]=numero;
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			numero=i*100+j*10+i;
			if (eh_primo(numero)) {
				v[cont++]=numero;
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				numero=i*10000+j*1000+k*100+j*10+i;
				if (eh_primo(numero)) {
					v[cont++]=numero;
				}
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		if (i==5) {
			i=7;
		}
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				for (l=0; l<=9; l++) {
					numero=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i;
					if (eh_primo(numero)) {
						v[cont++]=numero;
					}
				}
			}
		}
	}
	for (i=0; i<cont; i++) {
		if (v[i]>=min&&v[i]<=max) {
			fprintf(out, "%d\n", v[i]);
		} else if (v[i]>max) {
			fclose(out);
			return 0;
		}
	}
	fclose(out);
	return 0;
}

Agora vou prosseguir com o treinamento do USACO Training Gateway na seção 1.3, a começar pelo problema Mixing Milk.

Nos últimos dias não aconteceu nada demais. Só fiquei emocionado por ter recebido um 9,1 em biologia… :lol: E outra coisa legal também é que eu reli O Homem que Calculava e achei muito legal. Eu tinha lido na sexta série e acho que não tinha entendido direito tudo. O livro é muito bom e não é muito complicado não. O próximo que eu quero reler é O Diabo dos Números. Esse é mais “avançado” que o primeiro. Tô fazendo um trabalho de escola (de história) sobre (o filósofo) Pitágoras. É bem legal, o cara era muito bom. Na verdade, o trabalho tá virando de matemática, mas é bem interessante. É legal ter um professor de história que dá aula… ;) Não é igual ano passado, né? Tô achando bem legal os períodos da Grécia Antiga.

Ah, e vou finalizar citando um trecho d’O Homem que Calculava em homenagem ao Vavá, que não respira oxigênio… :D

Conta-se que o famoso rei Salomão, para demonstrar a finura e a sabedoria de seu espírito, deu à sua noiva, a rainha de Sabá – a famosa Belquiss – uma caixa com 529 pérolas. Por que 529? Sabe-se que 529 é o quadrado de 23, isto é, 529 é igual a 23 multiplicado por 23. E 23 era, exatamente, a idade da rainha.

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