A prova de segunda fase da Olimpíada Brasileira de Informática aconteceu há duas semanas e eu havia me esquecido de comentar aqui no blog como eu fui. O resultado deve sair amanhã ou depois de amanhã, segundo um dos caras responsáveis pela organização no orkut. Se tudo der certo e Éris quiser eu participarei pela quarta vez do curso de programação e da seletiva para a IOI.

Telemarketing (OBI2007 – Programação Nível 2 – Segunda Fase)

A solução mais eficiente usa heaps. Sem conseguir pensar nesta solução no momento da prova, implementei uma força bruta bem otimizada. Infelizmente, ela tem um pequeno erro que uma alma boa que se apresenta como CEO da Oracle encontrou para mim:

No seu programa, você faz um “for” que vai de “ultimo” até “n”, armazenando o id do vendedor que vai ficar desocupado primeiro na variável “mt”. Então você faz um “for” de 1 até “ultimo” mudando a variável “mt” apenas quando o vendedor ficar livre antes do “mt”, sendo que, como o id dele é menor, deve atender a ligação caso fique disponível antes ou ao mesmo tempo em que o vendedor “mt” ficar livre. Para resolver isso, fiz um “for” que vai de “ultimo” até 1 usando um “if” com “<=”.

Acredito que receberei no máximo 20/100 pontos.

#include <stdio.h>
#include <values.h>

#define NMAX 1010

int main() {
	int n, l, duracao, c=0, ocupado[NMAX], mt, ligacoes[NMAX], oc;
	int i, j, ultimo;

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

	for (i=1; i<=n; i++) {
		ocupado[i]=0;
		ligacoes[i]=0;
	}

	ocupado[0]=MAXINT;
	ultimo=0;

	for (i=1; i<=l; i++) {
		scanf("%d", &duracao);
		c=0;
		mt=0;
		for (j=ultimo+1; j<=n; j++) {
			if (!ocupado[j]) {
				ocupado[j]=duracao;
				ligacoes[j]++;
				c=1;
				ultimo=j;
				break;
			} else {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
		}
		if (!c) {
			for (j=1; j<=ultimo; j++) {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
			oc=ocupado[mt];
			ultimo=0;
			for (j=1; j<=n; j++) {
				ocupado[j]-=oc;
			}
			ocupado[mt]=duracao;
			ligacoes[mt]++;
		}
	}

	for (i=1; i<=n; i++) {
		printf("%d %dn", i, ligacoes[i]);
	}

	return 0;
}

Pizza (OBI2007 - Programação Nível 2 - Segunda Fase)

A solução mais eficiente usa programação dinâmica. A minha solução é uma força bruta, mais simples impossível. O programa está correto, mas não passará em muitos casos de teste por estourar o tempo limite. Espero mais uns 20/100 pontos.

#include <stdio.h>

#define MAX 100010

int main() {
	int n, soma;
	int i, j;
	int k[MAX];
	int maximo=0;

	scanf("%d", &n);
	for (i=1; i<=n; i++) {
		scanf("%d", &k[i]);
		k[i+n]=k[i];
		if (k[i]>maximo) {
			maximo=k[i];
		}
	}

	if (maximo==0) {
		printf("0n");
		return 0;
	}

	for (i=1; i<=n; i++) {
		soma=0;
		if (k[i]>0) {
			for (j=i; j<i+n; j++) {
				soma+=k[j];
				if (soma>maximo) {
					maximo=soma;
				}
			}
		}
	}

	printf("%dn", maximo);

	return 0;
}

Labirinto (OBI2007 - Programação Nível 2 - Segunda Fase)

O único problema que resolvi de maneira eficiente. A solução transforma o problema do labirinto em um grafo e depois chega à solução com uma busca em largura. Nesse eu espero a pontuação máxima, 100/100 pontos.

#include <stdio.h>
#include <values.h>

#define NMAX 55
#define VERTICES 2510

int n, m;
int nivel[VERTICES], vizinhos[VERTICES];
int fila[VERTICES*VERTICES], nvl[VERTICES*VERTICES];
int max[VERTICES];
int grafo[VERTICES][VERTICES];
int saida=MAXINT;

int identificador (int a, int b) {
	return (b+(a-1)*m);
}

int rn (int nivelerrado) {
	while (nivelerrado>9) {
		nivelerrado-=10;
	}
	return nivelerrado;
}

int main() {
	int i, j;
	int idmax, atual, idv;
	int niv, nivv, niva;
	int ini, fim;

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

	idmax=n*m;

	for (i=1; i<=idmax; i++) {
		for (j=1; j<=idmax; j++) {
			grafo[i][j]=0;
		}
		vizinhos[i]=0;
		max[i]=0;
	}

	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			atual=identificador(i, j);
			scanf("%d", &nivel[atual]);
			if (i-1>0) {
				idv=identificador(i-1, j);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j-1>0) {
				idv=identificador(i, j-1);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (i+1<=n) {
				idv=identificador(i+1, j);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j+1<=m) {
				idv=identificador(i, j+1);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			grafo[atual][vizinhos[atual]++]=atual;
		}
	}

	ini=0;
	fim=0;
	nvl[fim]=0;
	fila[fim++]=1;
	while (ini!=fim) {
		niv=nvl[ini];
		if (niv<saida) {
			atual=fila[ini++];
			niva=rn(nivel[atual]+niv);
			if (atual==idmax) {
				if (niv<saida) {
					saida=niv;
				}
			} else {
				for (i=0; i<vizinhos[atual]; i++) {
					idv=grafo[atual][i];
					nivv=rn(nivel[idv]+niv);
					if (nivv<=niva+1&&niv+1>max[idv]) {
						nvl[fim]=niv+1;
						max[idv]=niv+1;
						fila[fim++]=idv;
					}
				}
			}
		} else {
			ini++;
		}
	}

	printf("%dn", saida);
	return 0;
}

Conclusão

O resultado da olimpíada deve sair amanhã ou depois de amanhã e a nota de corte deve ser entre 100 e 150 pontos. Pelos meus cálculos, eu devo ter feito 140 (20+20+100), o que talvez me classifique para a próxima fase. Mais notícias a qualquer momento ;)

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

Em breve, estarei divulgando o how-to: Como perder uma viagem, um curso e uma oportunidade de representar o Brasil numa olimpíada internacional por um erro de digitação… :(

Um dia depois do prazo que consta no regulamento, a Comissão Organizadora da OBI2006 divulgou o resultado da modalidade programação. Para minha surpresa, fiz 20 pontos: 10 no Lobo Mau e 10 no Penalidade Mínima.

No último post eu mencionei que estava mal no dia da prova e nem fiz o último problema, mas não esperava tão poucos pontos. Aí baixei os testes do problema Lobo Mau e, com poucos testes, percebi que o erro do meu programa estava na entrada. Os arquivos que a OBI está usando estão no formato DOS (tem um caracter estranho além do n a cada quebra de linha) e por isso o meu programa não pegava corretamente os dados (ele pega todos os caracteres da matriz com scanf(“%c”); e o caracter de quebra de linha da mesma maneira). Já mandei o pedido de correção ontem a noite mesmo e eles já disseram que vão recorrigir.

Maldito erro de digitação!

Agoca… O pcoblema sécio veio depois. Ao lec o ródigo da minha solução*, pecrebi que eccei um racartec no acgumento rondirional de um loop! Tcoquei um “r” (rê) poc um “c” (ecce) (veja a linha 63 do ródigo que está linkado no astecisro), racarteces que signifiravam as linhas e rolunas da matciz, cespertivamente. Maldito ecco de digitação!

Corrija a frase acima, JavaScript! (são as inutilidades que o vício em linguagens client-side pode fazer…)

Se eu não tivesse trocado esses caracteres, tiraria 30 pontos a mais do que eu já devo tirar com a solicitação das quebras de linha: 110 pontos, o suficiente para participar do curso e da prova Seletiva para IOI.

* Minha solução para o problema Lobo Mau: lobo.c (infelizmente esse arquivo foi perdido com o tempo)

Bom… Já que é a lógica do problema que é o desafio na OBI, vocês não acham que erros de digitação deveriam poder ser corrigidos? Além disso, acho que eles podiam somar essa nota com a nota da primeira fase (mesmo que ela tivesse um peso bem menor).

Eu já esperava ir mal, mas pensei que os 100 pontos do Lobo Mau estavam garantidos, pelo menos. :(

Por enquanto é isso aí… Me ferrei, mas agora pelo menos nunca mais vou errar uma coisa dessas numa prova de programação e nunca mais vou comer no Mc Donalds antes de uma prova… (tô tentando ser otimista, mas tá difícil… hehehe) Parabéns pra quem passou e boa sorte! Embora eu não tenha gostado do resultado, na verdade não tenho motivos lógicos para reclamar. Vacilei na segunda fase mesmo e provas são sempre traiçoeiras (com certeza elas não são a melhor maneira de avaliação).

No primeiro artigo desta série, expliquei o que é um algoritmo e até citei exemplos do cotidiano, como acordar ou falar com outra pessoa. Talvez você nem tenha se dado conta, mas usando listas numeradas eu representei os algoritmos ali presentes, inclusive destacando a entrada e a saída de cada situação-problema. Porém, não é sempre assim que representamos algoritmos.

Não existe uma regra padrão para a representação de algoritmos. Cada pessoa escreve de forma diferente, mas o importante é ser legível e convencionado. Por exemplo, o livro Algoritmos: Teoria e Prática* traz nas páginas 14 e 15 convenções do pseudocódigo que utiliza no livro inteiro. Já eu, quando vou passar o mesmo algoritmo, utilizaria outro tipo de código, você pode utilizar outro, e por aí vai. Mas todos têm que ter o mesmo foco: legibilidade e fácil implementação para qualquer linguagem.

* A partir deste artigo, sempre que eu falar “Cormen”, “CLRS”, “Introduction to Algorithms” ou “Algoritmos: Teoria e Prática” estarei me referindo a um livro que é referência essencial nessa área. A versão que tenho (de onde tiro o número das páginas) é a tradução da segunda edição americana publicada pela Elsevier em 2002.

Os pseudocódigos costumam parecer um código em linguagem Pascal traduzido para a sua língua. :) Usam quase sempre estruturas que estamos acostumados a usar na programação, como se, enquanto, para, arrays, etc. Eles existem para que o algoritmo seja de fácil leitura para qualquer programador, que programe em qualquer linguagem “normal”. Veja o pseudocódigo do Insertion Sort, um algoritmo de ordenação de vetores bastante simples:

para j $\leftarrow{}$ 2 até comprimento do vetor, faça
 elemento $\leftarrow{}$ vetor[j]
 i $\leftarrow{}$ j - 1
 enquanto i > 0 e vetor[i] > elemento, faça
  vetor[i + 1] $\leftarrow{}$ vetor[i]
  i $\leftarrow{}$ i - 1
 fim-enquanto
 vetor[i + 1] $\leftarrow{}$ elemento
fim-para

(Não se preocupe em entender o que ele faz, AINDA, pois veremos isso mais adiante)

Se você programa em qualquer linguagem, você não terá dificuldade em traduzir esse pseudocódigo para ela. O pseudocódigo é sempre uma maneira bem simples de escrever o código. Veja por exemplo, o mesmo código em C:

for (j=2; vetor[j]!=NULL; j++) {
    elemento = vetor[j];
    for (i = j-1; i > 0 && vetor[i] > elemento; i--) {
        vetor[i+1] = vetor[i];
    }
    vetor[i+1] = elemento;
}

Você deve ter percebido que ao invés de usar três linhas com uma declaração, um condicional e um incremento, eu juntei todos num só for. Mas por isso o algoritmo é bem simples e sempre parte do princípio de que a sua linguagem é simples. Veja só a implementação do código em Pascal e compare-a com a do pseudocódigo:

for j:=2 to comprimento, do begin
    elemento := vetor[j];
    i := j-1;
    while i>0 && vetor[i] > elemento, do begin
        vetor[i+1] := vetor[i];
        i := i-1;
    end;
    vetor[i] := elemento;
end;

Linha por linha ela é exatamente igual! A única diferença é que o pseudocódigo é traduzido… Geralmente os pseudocódigos são parecidos sempre com essa base e suas implementações não são muito diferentes. E vai ser sempre dessa maneira que eu vou representar os algoritmos (usando pseudocódigos e alguns traduzindo para C para mostrar implementações). No entanto, qualquer dúvida sobre essa representação, fique a vontade para perguntar através dos comentários.

Acabou a OLIS e agora definitivamente o ano letivo. Comecei a rotina de estudos de leve… Por enquanto só relembrando aonde tinha parado: Brinquei um pouco de C, alocando memória, escovando bits até não aguentar mais; implementei alguns algoritmos em grafos (de problemas já anteriormente resolvidos, do site da OBI) e agora estou exercitando fluxos em rede. O primeiro passo foi me desviciar de usar busca em profundidade resolvendo vários programas anteriormente resolvidos de grafos agora com busca em largura e nessa próxima semana espero ter dominado o algoritmo de coloração, de bipartição e os fluxos em rede.

Pedi na Saraiva (temos que aproveitar o site inteiro em 12x sem juros e frete grátis) o livro Java – Como Programar, dos Deitel. Várias pessoas me recomendaram e acho que vai ser bom pra aprender Java de uma maneira mais “certinha” (não que pesquisando na internet não aprendemos de forma certa, mas com a didática de um livro tudo é bem mais fácil e a gente aprende as coisas numa ordem boa).

Estou acabando de reformular o site do Colégio, porque já que cada vez tem uma coisinha nova o design tava ficando muito cheio e o XHTML pouco acessível. Agora tá ficando mais clean e deve estar lá amanhã de tarde (só falta um pequeno detalhe: fazer funcionar em um troço da Microsoft que não pode ser considerado um navegador)

O que ando vendo por aí…

• Web Content Accessibility Guidelines 2.0
• Fixing the Back Button (em Ajax)
• Simulando latência com Greasemonkey
• Primeiro ano A: campeão-geral da OLIS!

… além dos meus feeds. Agora eu criei um perfil público no Bloglines (idéia do Zé) e vocês podem ver meus feeds aqui.