Arquivo da tag: programação dinâmica

There and back again…

ATENÇÃO: Este conteúdo foi publicado há 11 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.

Eu até tentei escrever um artigo por dia na semana passada, durante o curso da seletiva brasileira para a Olimpíada Internacional de Informática, mas não deu tempo… Então aqui vai um resumo feito uma semana depois do final do curso, separado em tópicos, com o título pouco criativo “There and back again…”

Nível mais alto

Comparando a prova da segunda fase da OBI2006 com a prova da OBI do ano passado, já era possível perceber que o nível esse ano subiu. E, como já esperado, o nível do curso e das pessoas também subiu, o que é excelente para o Brasil.

Mais prática, menos teoria

Neste ano não aconteceu a programação “normal” que tivemos nos últimos dois anos: aula teórica (só um professor apresentando slides e nós anotando, sem computadores) durante a manhã e aula prática durante a tarde.

Nos dois períodos nossas aulas foram no laboratório, com computadores, onde resolvemos uma porção de problemas do treinamento para a ACM da Universidade de Valladollid.

Criei uma pasta no meu servidor com todos os problemas que eu consegui resolver (alguns deles ficaram pela metade): http://tiagomadeira.net/pub/uva/.

Problemas sobre mais de um conteúdo

Uma característica interessante dos problemas desse ano (do treinamento e da prova) foi o uso de mais de um tipo de algoritmo para fazer a solução. A combinação mais comum foi geometria + grafos, que caiu inclusive na prova da Seletiva, no problema Labirinto.

A Prova

Primeiro Dia – Quadrado Romano

[Enunciado] 30 minutos tentando pensar em algum tipo de recorrência, 1h implementando uma solução força bruta! No final, pensei que faria uns 50 pontos (perderia um pouco por causa do tempo), mas perdi alguns pontos por resposta errada, ainda não sei por quê!

Solução: romano.c

Pontos: 10/100

Segundo Dia – Euros

[Enunciado] Durante as duas horas da prova fiquei procurando uma recorrência. Descobri que estou muito newbie em programação dinâmica. Não programei uma linha de código…

Pontos: 0/100

Terceiro Dia – Labirinto

[Enunciado] Olhei o enunciado e já saquei o que o problema queria. Eu tenho uma boa noção de grafos (embora precise estudar fluxos) e o curso trabalhou bastante algoritmos geométricos, então sem maiores problemas fiz o algoritmo, testei várias vezes, achei que ia tirar 100. No fim, não sei o que houve, se foi falta de tempo ou resposta errada. Só vi que fiz 40 pontos…

Solução: labirinto.c

Pontos: 40/100

Quarto Dia – Prova Final

[Caderno de Tarefas] Li todos os problemas e achei que poderia ir bem na prova (o primeiro problema eu tinha certeza que não conseguiria, mas o segundo e o terceiro dava pra fazer). Então, fui direto para o segundo problema, acreditando que era o mais fácil. Mas depois de bolar vários algoritmos, ter respostas erradas e tempos muito altos, tive que ficar com uma solução precária, um Floyd Warshall para cada troca de vértices (resultado: [tex]O(n^{5})[/tex]!) Aí depois não deu tempo de fazer o terceiro problema, mesmo eu tendo esboçado sua solução.

Solução do Teletransporte: tele.c

Pontos: 40/300

Conclusão

O legal é que esse curso sempre dá vontade de estudar, além de ensinar bastante… Aqui ficam registrados meus objetivos e metas pro segundo semestre de 2006 e primeiro semestre de 2007.

Objetivos

Metas

  • Comprar e ler Programming Challenges.
  • Estudar programação dinâmica. Conhecer os algoritmos mais comuns.
  • Estudar fluxos em rede e ordenação topológica.
  • Estudar matemática, inclusive recorrências e geometria (que não ajudam só para olimpíada de matemática, mas pras olimpíadas de informática também)

Curso da Seletiva IOI 2006: Primeiro Dia

ATENÇÃO: Este conteúdo foi publicado há 11 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.

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

EnunciadoMinha Solução

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

EnunciadoMinha Solução

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

EnunciadoMinha Solução

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

Férias!

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.

Hoje foi minha última aula desse ano e abertura da OLIS (olimpíada do meu colégio). Começaram extra-oficialmente as férias. Finalmente vou ter um tempinho pra poder estudar informática, matemática e música; aproveitar a praia, viajar, ler… Demorou, hein?

Como toda pessoa organizada (categoria que eu não me enquadro, mas estou tentando), fiz meu “plano” para aproveitar bem essas férias e também para decidir o que eu vou querer no ano que vem. Aqui embaixo está publicado, e sujeito a mudanças (porque meus objetivos sempre podem mudar). Notem também que eu coloquei algumas coisas como “ganhar olimpíada” que seriam conseqüência das outras ações. Além disso, eu coloquei alguns objetivos que podem parecer “sonhos”, mas acho que sempre é bom traçar objetivos difíceis pra tentar ir o mais longe possível.

Informática

Acho que foi a área em que eu menos evoluí nesse ano. É que é incrível que quanto mais eu aprendo, mais percebo que ainda tenho cada vez mais coisa a aprender. Isso não faz sentido matematicamente falando… A informática é desafiante e a gente sempre tem a impressão de que somos ignorantes. É como o Zeh falou num post em seu blog: “O mais legal de ser programador é olhar pra certas coisas que você fez no passado, que achava uma grande idéia, e perceber que aquilo era algo extremamente fedorento.”

Mas vamos lá…

  • Dominar os algoritmos mais básicos de grafos, programação dinâmica e geometria (saber implementá-los sem consulta em C).
  • Obter medalha de ouro na Olimpíada Brasileira de Informática.
  • Participar da Olimpíada Internacional de Informática.
  • Dominar o básico da linguagem C (saber gerenciar memória, usar bibliotecas como ncurses, usar sockets, etc.)
  • Aprender de vez a programar em C/GTK, para criar interfaces gráficas.
  • Dominar conceitos da orientação a objetos (abstração, encapsulamento, herança, poliformismo) e saber implementá-los em Java, C++ e PHP 4 e 5.
  • Aprender um JavaScript mais avançado (saber criar aqueles marquees por exemplo, ou como o cara pode arrastar um div pela tela) e exercitar essas linguagens client-side e Ajax dentro dos padrões web.
  • Saber diferenciar Unix/Linux/FreeBSD/OpenSolaris. Instalar estes outros sistemas no meu laptop.
  • Exorcizar o laptop. Não usar mais nem Flash, abolir o Windows.
  • Converter o laboratório de informática do Colégio Salesiano pra Linux (Edubuntu, que eu conheci essa semana e achei muito massa!).
  • Programar com frameworks.
  • Aprender Awk.
  • Aprender alguma coisa de hardware e de baixo nível (Assembler).

Matemática

Nesse ano, fui mal nas duas olimpíadas (brasileira e catarinense) e mesmo ganhando medalha de bronze na Olimpíada de Maio, não fiquei muito contente. De qualquer maneira, sinto que estou evoluindo na matemática graças as aulas do Vavá e mesmo as do Fabiano, que são lerdas mas às vezes trazem uma novidade.

  • Obter medalha de ouro na Olimpíada Regional de Matemática.
  • Obter medalha na Olimpíada Brasileira de Matemática.
  • Dominar geometria básica (decorar fórmulas dos volumes dos objetos, por exemplo).
  • Fazer exercícios dos Eureka!s
  • Fazer contas mentalmente mais rápido (exemplo: resolver uma Bháskara mentalmente em menos de 15 segundos)
  • Trabalhar com matrizes.
  • Trabalhar com funções de terceiro grau e superiores.
  • Trabalhar com números complexos.
  • Gabaritar a prova de matemática do vestibular do ITA no final do ano.
  • Prosseguir com treinamento para olimpíadas com o professor Vavá.

Física

Física depois desse ano entrando na minha lista de matérias legais e que eu preciso estudar bastante pra passar no ITA… Vamos à lista…

  • Dominar conceitos básicos e conhecer fórmulas básicas (Newton, Kelpler, Galileu, Einstein).
  • Revisar meu livro de física desse ano (2005).
  • Participar da Olimpíada Brasileira de Física.
  • Participar da Olimpíada Brasileira de Astronomia.
  • Prosseguir com grupo de estudos físicos com o professor Valdir.
  • Acertar 75% da prova de física do vestibular do ITA no final do ano.

Trabalho

Resolvi parar de trabalhar no Colégio, porque o salário era muito baixo (cerca de 200 reais é pouco, mesmo pra trabalhar 10 horas por semana) e o emprego fixo é muito chato (tem dias que eu vou lá e não faço nada, outros dias que tem um monte de coisa pra fazer e eu não consigo acabar nada; fora os alunos que vão lá no Lab. de Informática encher o saco – hehehe). Vou pegar mais freelances e acho que vou lucrar mais me dedicando só a isso e aos estudos, tanto financeiramente quanto nos aprendizados. Mas vou fazer uma proposta ao Colégio que é continuar mantendo o site deles (afinal, eles precisam de alguém pra fazer isso), mas fazer de casa e com isso só perder tempo quando precisar de alguma mudança, em casa!

Compras

Compras prioritárias que estou querendo fazer de livros e acessórios nesse ano… Aceito presentes! :D

Passeios e Cursos

Viagens [sendo] programadas…

  • Campinas – SP: Se tudo der certo, pra visitar meu irmão na UNICAMP e participar do Curso de Programação da OBI
  • Porto Alegre – RS: Fórum Internacional do Software Livre
  • Rio de Janeiro – RJ: Não tem nenhum evento não, mas eu queria conhecer.
  • México: Se tudo der certo, estamos lá na olimpíada internacional!

Música

No ano que vem, quero voltar a fazer aula de piano. Acho que farei com a mãe de uma amiga, que dá aula na ADMITA.


Nesse final de semana fomos pra Curitiba (quem acompanha meu feed viu as fotos no Flickr). Meu irmão Bruno fez vestibular pra música/violão na UNICAMP. Ele não achou a prova muito difícil e falou que acertou uns 80%. Ainda tem mais uma fase de prova de conhecimentos gerais e depois é a prova de aptidão (violão). Acho que ele passa… :)

Alguém tem notícias dos caras da UFSC? Já fizemos a final da Olimpíada Regional Catarinense de Matemática (por que eles não mudam o nome pra quem é de fora saber de onde que é e quem é de dentro não pensar que toda a Região Sul participa da olimpíada?) há dois meses, o ano já vai acabar, e NADA! (nem mesmo o gabarito da prova, mesmo sem o resultado final…)

Sempre que eu escrevo posts grandes, eu me perco no meio. Então se alguma parte ficou difícil de entender ou se tem algum erro de português aí, me avisem! :)

Mensageiros Instantâneos, OBM, Novos Programas, Música

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.

Em primeiro lugar, venho por meio deste post comunicar que não uso mais MSN Messenger. O mensageiro instantâneo da Microsoft saiu da minha lista de contas do CenterICQ para a entrada de dois novos e melhores: IRC e GoogleTalk/Jabber. Cheguei a conclusão de que quem quer falar comigo deve usar o que eu uso e não ao contrário, por um motivo óbvio: o meu é melhor que o deles.

Esta decisão fez com que eu perdesse centenas de contatos, mas acho que foi a decisão certa a ser tomada. Quem quiser me contatar agora, pode me adicionar no ICQ como 147330555, GoogleTalk como tmadeira em gmail.com e no IRC/Freenode, como tiagomadeira.

O segundo ponto importante deste post é o anúncio da OBM, Segunda Fase. A prova acontecerá no sábado que vem, dia 03 de setembro. Acho difícil eu conseguir medalha nesse ano (Terceira Fase é difícil!), mas vou tentar me esforçar o máximo possível… Esta semana tivemos o treino para olimpíadas com o Vavá, aprendi algumas coisas úteis. E ontem conversei com o César Kawakami no ICQ que me deu umas dicas interessantes também sobre Teoria dos Números. Vou tentar aprender alguma coisa sobre isso nos próximos dias…

As aulas de matemática dessa semana foram pouco produtivas porque eu andei faltando algumas para a divulgação do fórum do colégio. Então, só deu pra fazer dois problemas: a implementação da Máxima Subcadeia Comum (LCS/Programação Dinâmica):

//LCS - Longest Common Subsequence
//Programação Dinâmica - MSC - Maior Subcadeia Comum
 
#include <stdio.h>
#define SMAX 1001
#define DIAGONAL 1
#define LADO 2
#define CIMA 3
 
 
//n = tamanho de x
//m = tamanho de y
 
int c[SMAX][SMAX], b[SMAX][SMAX], n, m;
char x[SMAX], y[SMAX];
 
int lcs_recupera(int i, int j) {
	if (i==0||j==0) {
		return 0;
	}
	if (b[i][j]==DIAGONAL) {
		lcs_recupera(i-1, j-1);
		printf("%c", x[i]);
	} else if (b[i][j]==CIMA) {
		lcs_recupera(i-1, j);
	} else {
		lcs_recupera(i, j-1);
	}
}
 
int main() {
	int i, j;
 
 
	printf("LCS - Longest Common Subsequence\nPor Tiago Madeira\n\n");
	printf("Digite o tamanho da string X: ");
	scanf("%d", &m);
	printf("Digite o tamanho da string Y: ");
	scanf("%d", &n);
 
	scanf("%*c");
	printf("Digite a string X: ");
	for (i=1; i<=m; i++) {
		scanf("%c", &x[i]);
		c[i][0]=0;
	}
	scanf("%*c");
	printf("Digite a string Y: ");
	for (i=1; i<=n; i++) {
		scanf("%c", &y[i]);
		c[0][i]=0;
	}
 
	printf("\nPrograma raciocinando...\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			if (x[i]==y[j]) {
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=DIAGONAL;
			} else {
				if (c[i][j-1]>c[i-1][j]) {
					c[i][j]=c[i][j-1];
					b[i][j]=LADO;
				} else {
					c[i][j]=c[i-1][j];
					b[i][j]=CIMA;
				}
			}
		}
	}
 
/*	printf("\nMATRIX C\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", c[i][j]);
		}
		printf("\n");
	}
 
	printf("\nMATRIX B\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", b[i][j]);
		}
		printf("\n");
	}
*/
 
	lcs_recupera(m, n);
	printf("\n");
}

e um programa bem ridículo para calcular os termos e a soma de uma PA (é o que o prof. tá ensinando, aí achei bom pra fazer os exercícios mais rápido…):

//Aplicar as fórmulas das PAs
 
//Progressão Aritmética
//Programa desenvolvido por Tiago Madeira (c) 2005.
 
#include <stdio.h>
#define MAX 1000001
 
long double a[MAX], s[MAX];
 
int main() {
	long double r;
	int n;
 
	printf("Primeiro termo da PA: ");
	scanf("%Lf", &a[1]);
	printf("Razão da PA: ");
	scanf("%Lf", &r);
 
	//Eu podia fazer só pros que vão ser usados, mas não sei porquê, deu vontade de fazer assim... =)
	printf("\nAguarde o problema raciocinar tudo que ele tem para raciocinar...\n");
	for (n=2; n<MAX; n++) {
		a[n]=a[1]+r*(n-1);
		s[n]=(a[1]+a[n])*n/2;
	}
 
	printf("\nE agora, digite números para o programa dizer A e S dele.\n");
	do {
		printf("Número: ");
		scanf("%d", &n);
		if (!n) {
			break;
		}
		printf("Número na posição N = %.Lf\nSoma de 1 a N = %.Lf\n\n", a[n], s[n]);
	} while (n);
 
}

No começo do mês que vem é o Festival de Música de Itajaí. Acho que vou fazer oficina de Piano Popular avançado com o Prof. Michel Freidenson, que foi quem me deu aulas numa oficina semelhante há dois anos. A semana da música vai contar também com uns shows bem legais e o site oficial é este aqui.

Estatísticas, Programação Dinâmica, OBI Programação Nível 2

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.

Em primeiro lugar, quero dar a notícia de que as visitas do site só tem crescido. Nesse mês, o site tem recebido 100 ips únicos por dia e uns 500 hits. Para um pequeno blog, são estatísticas boas. As palavras-chave mais procuradas e a posição do meu site na procura por ela no Google (somente em português) são:

  • tableless – sétima posição
  • qemu – décima-primeira posição
  • problemas lógicos – quarta posição
  • dobradura – décima-sexta posição
  • gráfico de setores – décima-oitava posição
  • permutação – sexta posição
  • obi2005 – nona posição E “obi 2005” – terceira posição
  • biografia de linus torvalds – sexta posição emoticon

Ainda tem outras procuras interessantes e outras nada a ver, mas essas são as mais procuradas. É incrível como as pessoas clicam na minha biografia quando procuram pela biografia do criador do Linux! :blink: Acho legal as pessoas acharem meu site procurando por tableless, problemas lógicos, algoritmos, OBI2005 e nomes de problemas lógicos que eu fiz (também tem muita gente que procura por MMC e MDC).

Quanto a navegadores, o IE6 ainda tá dominando tudo. É uma pena que o pessoal use esse navegador pra entrar no meu site cujo um dos principais objetivos é apresentar os padrões web, tableless e faço de tudo pra acabar com o monopólio desse péssimo navegador e incentivar o software livre.

Por causa dos trabalhos, tenho programado muito em PHP, feito muitos designs no Fireworks (tô tendo que rebootar direto, porque desenho lá e depois venho pro Linux programar) e escrito XHTML/CSS. Alterei um pouco o programa ouvir (agora versão 1.1!). Ele já tá bem mais legalzinho do que aquela primeira versão que eu tinha postado e depois eu posto ele aqui.

Hmmm… Estive procurando umas coisas no livro vermelho (Algoritmos: Teoria e Prática) e descobri duas coisas desse livro.

  1. Ele tem tudo. É um livro completo, procura qualquer coisa de algoritmos ali que se acha tudo.
  2. É ilegível. :blink:

É muito complicado entender as coisas contidas nele, então tenho estudado um pouco por materiais na internet mais simples e só depois que peguei mesmo a coisa que leio no livro. Mas mesmo assim, bóio um pouco quanto a custos.

Por causa do problema Mochila (Pedido de Desculpas da OBI2005), acabei tentando aprender alguma coisa sobre programação dinâmica, mas não tô entendendo NADA! Só entendi o conceito e pra que serve, mas como fazer não sei. Não entendo como fazer as recorrências (e daí de repente, abro o índice do livro vermelho e acho lá um capítulo só sobre como fazer recorrências! – mas não entendo nada… :( )

Mas os outros problemas da OBI2005 Programação Nível 2 estão todos resolvidos! São bem fáceis. O único problema difícil do nível 2 da programação era esse de programação dinâmica mesmo… Publiquei eles na seção de scripts e vou fazer um pequeno comentário sobre cada um deles. Ah… E já que eu não peguei a prova de verdade (o Paulo Victor me passou um resumo dos problemas), não coloquei limites e saídas corretos.

Bafo

Um programa ridículo, igual o Cofrinhos da Vó Vitória (que foi o primeiro programa da OBI que eu fiz, quando tava começando a aprender C).

Solução:

//Bafo - OBI2005
#include <stdio.h>
 
int main() {
	int n, j1, j2, t1=0, t2=0, i, teste=1;
 
	while (scanf("%d", &n)&&n) {
		printf("Teste %d\n", teste++);
		t1=0;
		t2=0;
		for (i=1; i<=n; i++) {
			scanf("%d %d", &j1, &j2);
			t1+=j1;
			t2+=j2;
		}
		if (t1>t2) {
			printf("Aldo");
		} else {
			printf("Beto");
		}
		printf("\n\n");
	}
	return 0;
}

Transmissão de Energia

Um programa de grafos que busca ver se o grafo é conexo ou não. Uma simples busca de profundidade resolve.

Solução:

//Transmissão de Energia - OBI2005
#include <stdio.h>
#define NMAX 101
 
int g[NMAX][NMAX], achou[NMAX], n, achados;
 
void acha(int x) {
	int i;
 
	achou[x]=1;
	achados++;
	for (i=1; i<=n; i++) {
		if (g[x][i]&&!achou[i]) {
			g[x][i]=0;
			g[i][x]=0;
			acha(i);
		}
	}
}
 
int main() {
	int e, i, j, x, y, teste=1;
 
	while (scanf("%d %d", &n, &e)&&n) {
		achados=0;
		for (i=1; i<=n; i++) {
			achou[i]=0;
			for (j=1; j<=n; j++) {
				g[i][j]=0;
			}
		}
 
		for (i=1; i<=e; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]=1;
			g[y][x]=1;
		}
 
		acha(1);
 
		printf("Teste %d\n", teste++);
		if (achados==n) {
			printf("normal");
		} else {
			printf("falha");
		}
		printf("\n\n");
	}
 
	return 0;
}

Vivo ou Morto

Um jogo de Vivo ou Morto bem fácil de fazer mas difícil de explicar.

Solução:

//Vivo ou Morto - OBI2005
#include <stdio.h>
//Não sei qual o número máximo de jogadores!
#define NMAX 101
 
int main() {
	int jogador[NMAX], njogadores, nrodadas, i, j, k, vivos, ordem, fez;
 
	scanf("%d %d", &njogadores, &nrodadas);
	for (i=1; i<=njogadores; i++) {
		scanf("%d", &jogador[i]);
	}
	for (i=1; i<=nrodadas; i++) {
		scanf("%d %d", &vivos, &ordem);
		for (j=1; j<=vivos; j++) {
			scanf("%d", &fez);
			if (fez!=ordem) {
				jogador[j]=0;
			}
		}
		for (j=1; j<=vivos; j++) {
			if (!jogador[j]) {
				for (k=j; k<vivos; k++) {
					jogador[k]=jogador[k+1];
				}
			}
		}
	}
	printf("%d\n", jogador[1]);
}

Mini-poker

Um jogo chato… :lol: Uma baita falta de criatividade. Um programa não-lógico onde são dadas cinco cartas e eu devo determinar a pontuação do cara…

Solução:

//Mini-poker - OBI2005
#include <stdio.h>
 
int pontuacao(int c[]) {
	//Regra I
	if (c[1]==c[2]-1&&c[2]==c[3]-1&&c[3]==c[4]-1&&c[4]==c[5]-1) {
		return 200+c[1];
	}
 
	//Regra II
	if (c[1]==c[4]||c[2]==c[5]) {
		return 180+c[2];
	}
 
	//Regra III
	if ((c[1]==c[3]&&c[4]==c[5])||(c[3]==c[5]&&c[1]==c[2])) {
		return 160+c[3];
	}
 
	//Regra IV
	if (c[1]==c[3]||c[2]==c[4]||c[3]==c[5]) {
		return 140+c[3];
	}
 
	//Regra V
	if ((c[1]==c[2]&&c[4]==c[5])) {
		if (c[1]>c[4]) {
			return 3*c[1]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[1]+20;
		}
	}
	if ((c[1]==c[2]&&c[3]==c[4])) {
		if (c[1]>c[3]) {
			return 3*c[1]+2*c[3]+20;
		} else {
			return 3*c[3]+2*c[1]+20;
		}
	}
	if ((c[2]==c[3]&&c[4]==c[5])) {
		if (c[2]>c[4]) {
			return 3*c[2]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[2]+20;
		}
	}
 
	//Regra VI
	if (c[1]==c[2]||c[2]==c[3]) {
		return c[2];
	}
	if (c[3]==c[4]||c[4]==c[5]) {
		return c[4];
	}
 
	//Regra VII
	return 0;
}
 
int main() {
	int n, teste, c[6], carta, i, j;
 
	scanf("%d", &n);
	for (teste=1; teste<=n; teste++) {
		//Pega os valores e faz um Insertion Sort
		for (i=1; i<=5; i++) {
			scanf("%d", &carta);
			for (j=i-1; j>0&&c[j]>carta; j--) {
				c[j+1]=c[j];
			}
			c[j+1]=carta;
		}
 
		printf("Teste %d\n%d\n\n", teste, pontuacao(c));
	}
 
	return 0;
}

Saiu o gabarito da iniciação… Meu irmão, Lucas, acertou 14 no nível de quintas e sextas séries (ele tá na quinta) e ganhou Menção Honrosa. E o nosso, não vai sair não?