Não divulgarei minhas soluções (aka gabarito… :p) até sexta-feira, que é quando os professores já vão ter enviado a prova para a comissão organizadora da Olimpíada Brasileira de Informática.

Ontem, sábado 17 de março, foi a primeira fase da OBI. Eu resolvi a Iniciação Nível 1 para me divertir, vi a prova da Programação Nível 1 (que a Carol resolveu, com uma noção de C muito boa adquirida em um mês) e solucionei a prova da Programação Nível 2. Só vou falar sobre ela por enquanto, depois crio outros posts para falar sobre as outras.

Pra começar, a prova estava fácil. Eu resolvi em duas horas. Isso foi uma opinião de todos que fizeram a prova. Creio que estava mais fácil que a do ano passado. O caderno de tarefas era composto por cinco questões:

• Chocolate – Uma barra de chocolate é dividida várias vezes. O objetivo do programa é contar a quantidade de pedaços em que ela foi dividida. Basta ir pegando os números e ir somando-os -1.
• Repositório – Uma lista de números de programas e a versão em que estão instalados num computador. Depois, uma lista de números de programas e a versão em que eles estão disponíveis na internet. Decidir que programas devem ser atualizados no computador (determinar sempre a maior versão) e imprimí-los.
• Pastas – Dada uma lista de inteiros, verificar se os números aparecem a mesma quantidade de vezes (ex.: 1, 1, 2, 2, 3, 3 é válido; mas 1, 2, 2, 3, 3 não é).
• Móbile – Interpretei como um problema de grafos. Sabe o que é um móbile? Você tem que ver se todos as peças de um mesmo “nível” tem a mesma quantidade de filhos. Eu fiz um BFS (busca em largura) para determinar o nível de cada um e depois foi só ver se todos de cada nível tinham a mesma quantidade de filhos.
• Sacoleiro – Um cara quer comprar presentes para seus filhos. Em cada cidade há presente para um ou para outro, com preços diferentes. Ele quer ser justo. Seguindo um trajeto possível, passando por uma cidade e comprando um ou mais presentes ou até nenhum, qual a menor diferença possível entre os preços dos presentes? Sem dúvidas o problema mais difícil da prova (creio que o único difícil). Ainda não conheço a solução ideal, que deve usar programação dinâmica. Implementei um DFS (busca em profundidade) que testa todas as possibilidades.

No orkut já me disseram que cometi um erro ridículo:

No terceiro parágrafo do Repositórios, ele diz: “Um programa deve verificar então qual a versão de cada programa instalado nos computadores (todos eles possuem os mesmos aplicativos instalados e nas mesmas versões) e INSTALAR TODOS AQUELES QUE AINDA NÃO FORAM INSTALADOS ou cuja versão instalada seja anterior a versão mais recente.” Portanto, se um programa disponível na internet não está instalado nos computadores, ele deve ser instalado.

E meu Sacoleiro provavelmente não vai passar no tempo. Então espero 300 pontos e alguns quebrados.

O resultado sairá até o dia 7 de abril lá no site deles. Eu gero uma lista de classificação quando sair. :)

Estou no terceiro ano do Ensino Médio. Isso… aquele ano em que todos os professores na escola querem lhe preparar para o vestibular.

Confesso que o vestibular não é a coisa mais importante que tenho em mente e que há coisas que vocês diriam que tem bem menos importância que vem na frente na minha lista. Mas é melhor não confessar isso. Porque preocuparia minha mãe, minha namorada, minha família, meus professores, todo mundo, que talvez seja mais sábio do que eu por acreditar no futuro que todos acreditam… então é melhor deixar pra lá.

Deixando isso pra lá, vou partir do seguinte ponto: eu vou fazer vestibular no fim do ano. Eu quero passar. Sei lá se passarei! Isso não é problema meu, é da banca que vai corrigir a minha prova e não tô nem aí pra eles. Eu vejo as pessoas nervosas pra isso e não vejo muito sentido. Eu não passo de um número, se eu não passar ninguém vai morrer, o mundo não vai mudar e pode ser até melhor pra eu crescer mais antes de entrar.

Entrar numa universidade é legal, não só pelo aprendizado mas pela experiência de vida.

Creio que a visão de que faculdade é necessária pra um homem pensar é ilógica, conservadora e capitalista. Talvez admitam que não é pra pensar, é necessária pra ganhar dinheiro. Eu não creio que hoje em dia essa lógica seja tão verdadeira não. Mas entrar numa universidade, embora não seja necessária para nenhuma delas, pode ajudar nas duas coisas (pensar e ganhar dinheiro). Por isso, de qualquer maneira, eu quero entrar numa universidade. Eu gosto do ambiente, gosto de ter professores que podem me ajudar a pensar e creio que lá poderei me desenvolver melhor.

Então eu estava pensando em começar a carreira estudando computação. Porque:

1. Eu gosto disso
2. Eu sou muito bom nisso
3. Isso dá dinheiro

Quero fazer ciência da computação desde que aprendi o que é uma faculdade, e isso foi antes da terceira série, aos 9 anos, antes de quando eu fiz o meu primeiro site. Aí minha idéia atual é fazer Ciência da Computação na UNICAMP e talvez tentar transformá-la no meio do ano em Computer Science no MIT. A idéia de fazer na USP também está me gustando bastante. Não sei se é possível fazer vestibular na USP e na UNICAMP. Alguém sabe me responder?

Depois eu penso em fazer filosofia e/ou psicologia, também na UNICAMP ou na USP. Não tem nada a ver com a minha área – não é o que eu quero fazer pra ganhar dinheiro. Isso é ruim?

Mas vou retomar o segundo parágrafo, porque não vou agüentar passar esse texto sem escrever sobre aquilo.

É que você sabe o que é engraçado? Nós queremos mudar o mundo, mas queremos ficar ricos. Quando você me pergunta sobre o meu futuro, eu digo que eu viverei sem problemas financeiros com a Carol e meus filhos, todos seremos felizes… Eu trabalhando em casa (ou em viagens), programando, pensando, escrevendo. Quando você me pergunta sobre o futuro do mundo, eu digo que vai acabar em 50 anos se continuar do jeito que está. O planeta está numa situação alarmante, mas mesmo assim nós continuamos com as nossas atividades normais.

Somos tão egoístas… A minha pergunta é o que vou fazer quando crescer e não o que o mundo vai ser quando eu crescer. E, se sou uma pessoa solidária, que valorizo inclusive os pensamentos daquele filósofo que a maioria da população chama de Deus (um tal de Jesus), não deveria pensar assim.

E é por causa dessa falta de egoísmo que me vem às vezes que eu não me preocupo com a minha faculdade. E aí quem me conhece se preocupa comigo. O mundo não é tão pequeno assim, gente. Eu hoje estou com uma dificuldade gigantesca em ver o mundo dos meus olhos. Talvez eu precise de terapia. Talvez o resto do mundo é que precise. Pra acabar com essa contradição, com essa hipocrisia e com esse egoísmo sem sentido.

No momento não consigo ser epicurista. O que eu quero ver é um mundo melhor. Para todos. Eu não passo de um no meio de seis bilhões. Isso não significa que eu queira ser um mártir; eu quero ser como todos os outros 1/6.000.000.000 (vejam como esse número é grande!) Ou pelo menos um mundo, mesmo que não seja perfeito, mas que exista. Um mundo que não acabe em menos de 100 anos. Talvez eu devesse me mudar para a Venezuela e servir para o presidente Hugo Chávez. Por mais incrível que possa parecer, eu me sentiria bem. Não, não sou socialista. Eu não gosto do socialismo, mas acho melhor que deixar o mundo acabar na mão dos imperialistas ianques.

Eu lutaria contra os Estados Unidos (acho que minha ajuda poderia ser mais útil na inteligência do que no mano-a-mano, mas anyway…). Me sentiria ridículo por estar colocando gravata para mudar o mundo dos engravatados (John Lennon, aprendi com o Reverendo), mas estaria mudando o mundo. Ou será que não devo me preocupar com nada disso, deva me focar só no meu vestibular, viver no meu pequeno mundo, pra fazer minha faculdade de computação e ganhar dinheiro ou mudar o mundo só a base de construção de softwares?

Não que a construção de softwares não possa mudar o mundo. Eu quero mudar o mundo com programas. Os programas são bem menos falhos que homens. Tem gente que me acha imbecil por ser totalmente a favor da substituição de mão-de-obra compulsória por máquinas. Se seu trabalho pode ser feito por máquinas, que seja feito por elas. Elas fazem melhor que você.

Quando o meu professor de física passou uma tarefa pedindo para converter graus de celsius para kelvin, farenheit, etc, etc, etc, eu não fiz. Pelo amor de Google, isso é trabalho pra máquina. Já trabalho pra homem deve ser aquele trabalho criativo, que a inteligência artificial ainda está longe de fazer, porque ainda nós (enquanto homens) não conseguimos criar coisas como cérebros humanos.

De qualquer maneira, é o meu vestibular que vai mudar o mundo? Será que eu devo mesmo me preocupar em passar? Eu já disse que gosto da universidade e de seu ambiente e que quero estudar, mas eu deveria me preocupar da maneira que as pessoas inteligentes se preocupam? O meu futuro é tão importante assim pra vocês, pro mundo? E se for, é por causa da sua graduação? Acho que não.

Aí no meio de tudo isso, mergulhado nesses pensamentos sobre o meu futuro e o futuro do mundo, chegou a professora ao meu lado e me perguntou hoje na aula: você já sabe que curso você vai fazer?

Eu sei lá o que eu quero. Eu, eu, eu, eu, eu… Nem sei quem eu sou, como eu vou saber quem eu quero ser? Desisto. Eu respondi a professora, com a cara mais normal que consegui representar: “Ciência da Computação na UNICAMP”. Na minha cabeça, eu concluí: “E enquanto isso, um monte de gente perde o futuro, os ianques continuam com seus genocídios e o nosso mundo chega mais perto do seu fim.” Mas isso com certeza não é nem um pouco importante perto da minha graduação.

IMPORTANTE: Esse post não é recomendado pra quem nunca programou. Escrevi sem pensar neles… :-)

Bom… Existem pessoas que sabem programar e não programam. O difícil na arte de programar é pensar, porque o resto é escrever em inglês e se acostumar com uma sintaxe rigorosa.

Comecei ontem a ensinar um amigo a programar em C para participar da OBI 2007, que foi anunciada nessa semana. Eu poderia ensinar Pascal, que é mais que suficiente para olimpíadas (quem conhece o André Linhares entende o que eu quero dizer…), mas resolvi ensinar C porque eu me embabacaria no Pascal e no C eu vejo os blocos mais “definidos” com as chaves; aqueles begins e _ends “sujam” o código. E como diz o lema do sistema desse blog, \code is poetry_.

O reverendo e meus leitores mais novos devem estar se perguntando: como o Tiago é capaz de fazer essas loucuras? É verdade que fiquei um bom tempo sem escrever sobre programação, mas adoro isso! É lazer pra mim e essa também é a minha profissão, já que eu não consigo viver desse blog (por culpa sua que não clica nos meus anúncios…). Só quando começo a brincar é que lembro como é divertido e acho que é porque eu me sinto “no poder”. :-)

Mas voltando ao assunto… Esse meu colega é campeão regional de matemática e tem uma facilidade incrível para matérias exatas (e pras humanas mais ainda, eu acho). Eu estava sem nada pra escrever aqui no blog e resolvi escrever sobre o que eu vou ensinar pra ele amanhã: arrays e for.

Meu aluno está resolvendo a prova da Programação Nível 1 da OBI2005. Ele já resolveu a Frota de Táxi e agora precisa resolver o problema Campos de Minhoca.

O problema é que, pela primeira vez, ele se depara com uma situação em que tem que receber como entrada uma tabela completa! Sugeri que ele usasse dois while, um dentro do outro. Ele pensou um pouco e conseguiu fazer o seguinte código:

scanf("%d %d", &n, &m);

natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor);
		matual=matual+1;
	}
	natual=natual+1;
}

Perfeito. Era o que eu queria que ele fizesse. Mas agora entenda sua situação: como armazenar todos esses números pra depois trabalhar com eles?

Dessa maneira, cada vez que recebemos um novo elemento da tabela, colocamos numa variável valor e ao final do recebimento da entrada ficaremos apenas com o último elemento da tabela.

E então entram os arrays…

Arrays são matrizes de matemática ou, numa língua muito mais fácil, tabelas. Vamos supôr que eu receba 1000 valores e queira saber qual é o maior deles. Imaginem como seria para declarar suas variáveis, recebê-los e tratá-los:

int var1, var2, var3, var4, ..., var1000;

scanf("%d", &var1);
scanf("%d", &var2);
scanf("%d", &var3);
scanf("%d", &var4);
...
scanf("%d", &var1000);

if (var1>maior) {
	maior=var1;
}

if (var2>maior) {
	maior=var2;
}

if (var3>maior) {
	maior=var3;
}

...

Impossível! Totalmente inviável. Então alguém teve a brilhante idéia de criar um elemento que guarda várias variáveis de uma vez. Então surgiram os arrays. Você cria uma só variável e na sua declaração coloca o número de elementos que ele tem dentro de chaves.

int var[1001];

Depois para receber os valores você pode então simplesmente usar o while como usou no exemplo do Campos de Minhoca:

int var[1001], indice;

indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

E para ver qual é o maior deles basta usar mais um while:

indice=1;
while (indice<=1000) {
	if (var[indice]>maior) {
		maior=var[indice];
	}
}

Mas peraí… Então como faríamos no Campos de Minhoca? Lá não temos só uma lista de N números, mas uma tabela mesmo, com altura e largura. É simples, basta fazer com que cada índice dessa lista seja outra lista.

int tabela[1001][1001];

Assim, podemos acessar todos os elementos e pra saber o elemento da coordenada 5, 23 basta usar a variável tabela[5][23].

Aí aquele primeiro código do Campos de Minhoca torna-se:

scanf("%d %d", &n, &m);

natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor[natual][matual]);
		matual=matual+1;
	}
	natual=natual+1;
}

As variáveis [n,m]atual vão crescendo e preenchendo a tabela. :)

Só que acontece que se programássemos dessa maneira gastaríamos uma porção de códigos e ficaríamos confusos pra trabalhar com arrays, tendo que sempre verificar os índices e acabaríamos errando bastante. Então criou-se o for. O for é uma simplificação desse tipo de while. Você diz que:

para todo natual de 1 a n, faça:
	alguma coisa
fim-para

Escrever for em Pascal é super divertido, porque você se sente falando com o computador:

for i:=1 to 100, do begin
	código aqui
end;

No C existe uma sintaxe mais versátil, mas que pode ser um pouquinho mais difícil de entender no início:

for (atribuição; condição; incremento)

A atribuição é onde você coloca o primeiro valor do índice. A condição é a condição para que o enquanto continue funcionando. O incremento é o que ele deve fazer ao final de cada loop (geralmente é aumentar um).

Então, ao invés de fazer esse while:

indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

Você pode escrever:

for (indice=1; indice<=1000; indice=indice+1) {
	scanf("%d", &var[indice]);
}

E como resolver a parte da entrada do Campos de Minhoca sabendo disso?

Simples… Basta colocar um for dentro do outro:

scanf("%d %d", &n, &m);

for (i=1; i<=n; i++) {
	for (j=1; j<=m; j++) {
		scanf("%d", &matriz[i][j]);
	}
}

Observação 1: Escrever variavel++ é a mesma coisa que escrever variavel=variavel+1.

Observação 2: Geralmente utiliza-se i para o primeiro for, depois j, k, l e eu nunca tive que passar do l. :)

Observação 3: Se eu queria um vetor de 1000 posições lá em cima, por que eu declarei 1001? Bom… O C conta a partir de 0. Quando eu peço 1000, ele vai me dar um vetor de 0 a 999. Já que eu queria ter o var[1000] eu precisei declarar de 1000+1=1001.

Ficou claro ou muito confuso? Se deu pra entender isso aí, agora é só mandar a ver no resto do problema! :)

Venho percebendo que o Atum está fora do ar, então fiz uma busca no cache do Google para copiar um documento que não poderia ser perdido: as parábolas de Xico Xavier, o maior programador da história. Estavam no wiki do Ribamar, um cara que conheci em Campinas em 2004 e que me apresentou três dos meus softwares preferidos: Slackware, Mutt e LaTeX. Nem pedi autorização dele para copiar essa página, mas espero que ele não se importe… :) Não modifiquei absolutamente nada no texto.

Eu até tentei escrever um artigo por dia na semana passada, durante o curso da seletiva brasileira para a Olimpíada Internacional de Informática, mas não deu tempo… Então aqui vai um resumo feito uma semana depois do final do curso, separado em tópicos, com o título pouco criativo “There and back again…”

Nível mais alto

Comparando a prova da segunda fase da OBI2006 com a prova da OBI do ano passado, já era possível perceber que o nível esse ano subiu. E, como já esperado, o nível do curso e das pessoas também subiu, o que é excelente para o Brasil.

Mais prática, menos teoria

Neste ano não aconteceu a programação “normal” que tivemos nos últimos dois anos: aula teórica (só um professor apresentando slides e nós anotando, sem computadores) durante a manhã e aula prática durante a tarde.

Nos dois períodos nossas aulas foram no laboratório, com computadores, onde resolvemos uma porção de problemas do treinamento para a ACM da Universidade de Valladollid.

Criei uma pasta no meu servidor com todos os problemas que eu consegui resolver (alguns deles ficaram pela metade): tiagomadeira.net/pub/uva/ (essa pasta infelizmente foi perdida com o tempo).

Problemas sobre mais de um conteúdo

Uma característica interessante dos problemas desse ano (do treinamento e da prova) foi o uso de mais de um tipo de algoritmo para fazer a solução. A combinação mais comum foi geometria + grafos, que caiu inclusive na prova da Seletiva, no problema Labirinto.

A Prova

Primeiro Dia – Quadrado Romano

[Enunciado] 30 minutos tentando pensar em algum tipo de recorrência, 1h implementando uma solução força bruta! No final, pensei que faria uns 50 pontos (perderia um pouco por causa do tempo), mas perdi alguns pontos por resposta errada, ainda não sei por quê!

Solução: romano.c (infelizmente foi perdido com o tempo)

Pontos: 10/100

Segundo Dia – Euros

[Enunciado] Durante as duas horas da prova fiquei procurando uma recorrência. Descobri que estou muito newbie em programação dinâmica. Não programei uma linha de código…

Pontos: 0/100

Terceiro Dia – Labirinto

[Enunciado] Olhei o enunciado e já saquei o que o problema queria. Eu tenho uma boa noção de grafos (embora precise estudar fluxos) e o curso trabalhou bastante algoritmos geométricos, então sem maiores problemas fiz o algoritmo, testei várias vezes, achei que ia tirar 100. No fim, não sei o que houve, se foi falta de tempo ou resposta errada. Só vi que fiz 40 pontos…

Solução: labirinto.c (infelizmente foi perdido com o tempo)

Pontos: 40/100

Quarto Dia – Prova Final

[Caderno de Tarefas] Li todos os problemas e achei que poderia ir bem na prova (o primeiro problema eu tinha certeza que não conseguiria, mas o segundo e o terceiro dava pra fazer). Então, fui direto para o segundo problema, acreditando que era o mais fácil. Mas depois de bolar vários algoritmos, ter respostas erradas e tempos muito altos, tive que ficar com uma solução precária, um Floyd Warshall para cada troca de vértices (resultado: [tex]O(n^{5})[/tex]!) Aí depois não deu tempo de fazer o terceiro problema, mesmo eu tendo esboçado sua solução.

Solução do Teletransporte: tele.c (infelizmente foi perdido com o tempo)

Pontos: 40/300

Conclusão

O legal é que esse curso sempre dá vontade de estudar, além de ensinar bastante… Aqui ficam registrados meus objetivos e metas pro segundo semestre de 2006 e primeiro semestre de 2007.

Objetivos

• Medalha de ouro na Olimpíada Brasileira de Informática do ano que vem.
• Visitar a Croácia representando o Brasil na Olimpíada Internacional de Informática do ano que vem.
• Vencer a Olimpíada Regional de Matemática (não dá pra ficar sem nenhuma medalha nesse ano, né?)

Metas

• Comprar e ler Programming Challenges.
• Estudar programação dinâmica. Conhecer os algoritmos mais comuns.
• Estudar fluxos em rede e ordenação topológica.
• Estudar matemática, inclusive recorrências e geometria (que não ajudam só para olimpíada de matemática, mas pras olimpíadas de informática também)