Arquivo mensais:junho 2005

Palíndromos Primos

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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

Prime Palindromes

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.

O Homem que Calculava

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.

Samba em Prelúdio

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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.
<?php
   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…

Primeiro Lugar na OBI 2005!

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Quadro de Mérito OBI2005 Programação Nível 1

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

Novo site!

ATENÇÃO: Este conteúdo foi publicado há 12 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Deixei o site fora do ar por dois dias para acabar de fazer esse design. E não refiz só o design. Refiz os bancos de dados, textos (links), adicionei a seção Portifólio e reprogramei todo o site. Agora eu cadastro posts em HTML, fazendo com que eu possa abusar mais de formatação nos artigos. Posso postar várias imagens tipo as da minha biografia (aliás, enchi minha biografia de fotos). Também fiz bastante mudanças nas expressões regulares do site.

GeSHi

Estou usando o GeSHi para sintaxe colorida dos códigos que posto aqui. O “teste oficial” é o post Samba em Prelúdio que traz trechos dessa música, do Vinicius de Moraes e Baden Powell, escritos em várias linguagens, de várias formas diferentes, com sintaxe colorida do GeSHi.

Ainda não tá pronto!

Já publiquei tudo aqui como oficial, mas o site ainda não está completamente pronto. Ainda não fiz o feed (embora ele esteja declarado no cabeçalho da página), não acabei a seção Portifólio e nem o sistema de emoticons aqui dos posts e comentários. Eu tinha feito, mas o problema é que tava colocando emoticons nos códigos… Por isso, ainda tô tentando descobrir como eu faço para só o que tá fora dos code passar pela função de emoticons e espero que tudo se normalize em breve.

Eu também não copiei todos os posts antigos para cá, mas estou fazendo isso, pela ordem da visualização e comentários dos posts. Os posts mais linkados em outros locais já foram copiados, como a falha no Fotolog.net, posts sobre permutação, etc.

Avaliação

Postei o site em alguns fóruns para ser avaliado. Ele é totalmente baseado em CSS, então eu posso vir a alterar alguns detalhes. Agora ele tá bem mais semântico e bem escrito do que o antigo, o que facilita essas mudanças. Postem suas críticas e sugestões aí nos comentários! ;)

Espero que gostem!