Curso da Seletiva IOI 2006: Primeiro Dia
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
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.
441 - Lotto
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
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.
Technorati Tags: OBI, IOI, Olimpíada, Informática, Lógica
Compare Preços de: iPod, home theater, plasma, lcd, câmeras digitais, games, ps3
Legal, Ti! Aproveite bem aí!
Muito boa esta prática de ir registrando as suas aprendizagens. Como professora, fico orgulhosa!
Como mãe, mais ainda! heheheh!
Oiieee
Noss, mais um que está participando no desafio nacional academico, ou o dna mesmo, o desafio mais longo de minha vida =P ^^, amei ter encontrado um relato sobre isso. Pelo jeito não foi só eu que achei dificil (nhan….. ediomas foi o pior…… eu sei um tanto de japones, mtooo pouco, e o meu grupo ficou quase um dia nisso ¬¬).
Boa sorte para o teu grupo, se vc n poder resolver.
Eu estou tentando resolver ^^
=*
Fala Tiago…
Achei a prova de hoje no nível da segunda fase, embora eu não tenha resolvido 100%
Quando eu saí, restavam 8 minutos e todos ainda permaneciam fazendo a prova.
Submeti minha solução que, ao ir para a casa, percebi que, além do custo poder ser alto, esqueci de checar quando estiver nas extremidades. (Que besta, mas fiquei tão contente - e cansado - quando vi que a solução funcionou que submeti e fui indo para casa)
Abraços e até amanhã.
Será que somos parentes? Estava vendo se o google achava minha página e achei a sua.
Quando era moleque também gostava de olimpíadas de matemática, mas nunca fui muito longe e desencanei.
Vendo que você ajuda os ineptos e abusando já que talvez até sejamos parentes, pergunto:
você já mexeu com o nxclient, da nomachine? uso ubuntu dapper em casa e quero acessar o desktop do micro no trabalho (o vnc do kde é muito lento). Ele estabelece a conexâo bonitinho, mas nâo lança a tela no windows…
Se estiver difícil, nâo esquenta. Abraço,
Wagner