Tiago Madeira » 2005

24/06/2005

Palíndromos Primos

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

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.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Escreva um comentário!

17/06/2005

Samba em Prelúdio

GeSHi Highlight funcionando! Página "oficial" de testes...

#include <stdio.h>
int main() {
   printf("Eu sem você");
}

program continuacao;
 
begin
   write('Não tenho porquê.');
end.

echo "Porque sem você..."; ?>

<html>
   <head>
      <title>Continuação</title>
   </head>
 
   <body>
      <p>Não sei nem chorar...</p>
   </body>
</html>

#!/bin/bash
 
echo "Sou chama sem luz..."

.jardim {
   sem:luar;
   luar:sem amor;
   amor:sem se dar;
}

document.write("Eu sem você...");

print 'Sou só desamor.'

INSERT INTO musica (letra) VALUES ('Um barco sem mar...');

<%
response.write("Um campo sem flor.");
%>

<?xml version="1.0">
 
<window id="janela" title="Continuação em XUL" xmlns="http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul">
<text id="resto" value="Tristeza que vai, tristeza que vem" />
</window>

E por aí vai... Heheh...

Compare Preços de: iPod, home theater, plasma, lcd, câmeras digitais, games, ps3

Um comentário...

17/06/2005

Primeiro Lugar na OBI 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 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 "\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

Compare Preços de: iPod, home theater, plasma, lcd, câmeras digitais, games, ps3

Um comentário...

Assine via RSS

Assine gratuitamente o meu blog e receba todas as atualizações na hora, em seu agregador de feeds favorito.

Seja o 231º assinante

Busca no blog

Escreva palavras-chave para buscar e clique em Pesquisar.

Páginas

Veja também...

Blogs de minha autoria

1001 Gatos de Schrödinger (discordianismo e mindfuck)
Algoritmos computacionais (estudo para olimpíadas e aprendizagem sobre lógica de programação)

Tiago Madeira Inferências aleatórias de um cérebro em versão alpha

Arquivo do mês: June, 2005