Lógica « Legacy tiagomadeira.net

Archive for the ‘Lógica’ Category

Bronze na Olimpíada de Maio

Tuesday, August 2nd, 2005

Ontem saiu no site da OBM o resultado do Brasil na Olimpíada de Maio nesse ano. Ganhei bronze com 30 pontos! Mais um bicampeonato nesse ano… Hehehe… :D

Nessa semana, o laptop voltou a ter um problema de HD (quer dizer, o problema é o mesmo que aquela vez, mas voltou a dar pau e eu tive que formatar tudo de novo!). Tô revoltado aqui, ainda mais porque nessa semana tô refazendo as provas e trabalhos da semana que eu faltei por causa do curso da OBI. Tenho um trabalho (Flash, The Little Dog Corporation) sobre o Pitágoras que devo acabar até sexta-feira e não tô nem com um sistema estável aqui…

Não sei ainda o que vou fazer com o laptop. Eu mandei um e-mail pra HP e o cara (muito educado e rápido, por sinal) respondeu sugerindo que eu fizesse três coisas. Primeira: tirar e colocar o HD de novo. Segunda: rodar o “Killdisk”. Terceira: comprar um hd novo! :( Tomara que não seja a última, porque um HD de 40gb pro laptop tá 350 reais…

A parte boa é que já que eu formatei, eu acabei reconfigurando tudo e daí eu sempre acabo aprendendo algo novo. Dessa vez, eu parei de vez de usar KDE (nem instalei pra não dar vontade). Tô usando Fluxbox com Eterm e aprendi a deixar o Fluxbox bem bonito… Depois eu vou ter que formatar o HD para qualquer uma das sugestões do cara da HP, então vou ter que configurar tudo de novo, mas foi legal só pra aprender…

Não tenho mais programado NADA (com exceção de durante as aulas de matemática, porque o professor ainda tá ensinando como descobrir vértices de funções de segundo grau), mas baixei uns PDFs legais do professor Cid da UNICAMP e vou ler esse material assim que possível (sobre NP-Completude e Programação Dinâmica).

O Colégio tá inaugurando um fórum novo. Quem estiver disposto a contribuir com dúvidas ou respostas: Quer saber?

Para quem não sabe…

A Olimpíada de Maio é uma olimpíada iberoamericana (acontece em países colonizados por Portugal e Espanha, e nestes dois países também) de matemática dividida em dois níveis: Até 13 anos e até 15 anos. Este ano eu participei do nível 2, 15 anos.

Esta notícia em outros lugares…

Posted in Lógica | No Comments »

Resultado da Seletiva IOI

Sunday, July 24th, 2005

Hoje cheguei em Itajaí pela manhã depois de uma semana muito legal visitando pontos turísticos e participando de eventos de vários tipos em São Paulo (as fotos estão disponíveis no meu álbum do Flickr).

Perto da hora do almoço, o resultado da seletiva para a Olimpíada Internacional de Informática finalmente saiu. E me surpreendi com a pequena quantidade de pontos que fiz. Eu tinha feito as seis questões e esperava fazer uns 400 pontos (sabia que o problema do Caixeiro Viajante da primeira prova estava errado e considerava alguns errinhos), mas fiz apenas 180! :(

Só fiz 10 pontos no problema Campos de Minhoca e 40 no Criptologia, entre outras coisas inesperadas como o Floyd Warshall não ser suficiente para resolver o problema do Caixeiro Viajante da segunda prova, como eu pensava… E pior é que em todos os testes cai ao menos um caso que meu programa não cobre!

Mas a maior decepção foi mesmo no Criptologia. É um problema bem fácil de substituição de caracteres… Eu não fiz os 100 pontos possíveis por não imprimir um espaço no começo da frase caso tivesse. Acho que isso não tá certo, já que uma frase (mensagem) NUNCA começa com um espaço e meu programa está imprimindo tudo conforme solicitado, com exceção desse espaço. (E o Tchê disse na Tutoria que a falta de um espaço não deveria tirar pontos na olimpíada.) Por isso, enviei um e-mail solicitando recorreção e admissão disso. Pelo resultado atual, estou em nono lugar e com os 60 pontos desse problema eu fico em quinto. Já é uma diferença boa e acho bem mais legal ficar só a uma vaga de estar na internacional…

Editado – Quinto lugar

A coordenação da OBI aceitou meu pedido e agora estou em quinto lugar com 240 pontos! Ou seja, se alguém não puder ir por compromisso ou saúde, acho que sou eu que participo da equipe brasileira no lugar dele. :D Bem que podia ter mais uma coisinha assim com mais 50 pontos, né? :lol:

Agora tô começando a me preparar pro ano que vem.

Pretendo rever os slides do curso, ler o livro do Cormen, estudar mais matemática/geometria e resolver os problemas do USACO Training Gateway e da Universidade de Valadollid pra ver se consigo ir pro México ano que vem… Acho que tenho bastante chances (aliás, descobri que nesse ano eu já tinha, mas por errinhos não fui tão bem como pensei que tivesse ido).

O curso desse ano foi bem interessante, aprendi bastante e mesmo não indo tão bem na seletiva, agora estou animado pro ano que vem. :D

Semana Azul

Vou estender o tópico para fazer uma propaganda da Semana Azul. A Semana Azul é um evento on-line que ocorre entre 25 e 31 de julho de 2005. Para acessar as palestras que acontecem todos os dias da semana às 20h00, o participante precisa ter algum cliente de IRC e entrar na rede da Freenode (irc.freenode.net) no canal #mozilla-br. Irão ocorrer palestras legais sobre projetos que envolvem XUL e Mozilla… A programação completa está disponível aqui: http://www.mozilla.org.br/semanaazul/?n=SAr1.ProgramacaoIRC. :) Participem!

Posted in Lógica | No Comments »

Curso de Programação Avançada na UNICAMP

Thursday, July 14th, 2005

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

Posted in Lógica | No Comments »

Palíndromos Primos

Friday, June 24th, 2005

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.

Já publiquei o código-fonte do programa na seção de resolução de problemas lógicos como pprime.c e 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.

Posted in Lógica | No Comments »

Primeiro Lugar na OBI 2005!

Friday, June 17th, 2005

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 "\34m\1mO site da OBI não foi atualizado desde a última vez que o programa foi executado.\0m" else echo "\31m\1mO site da OBI foi atualizado desde a última vez que o programa foi executado!\0m" 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>/\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 "\34m\1mVerificando id $i...\0m" 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

Posted in Lógica | No Comments »