Programando melhor: Revisão
Olá pessoal!
Como a prova da primeira fase da OBI é amanhã resolvi fazer esse post para uma revisão rápida de vocês sobre algumas questões importantes.
Primeiramente, quero avisá-los para termos bastante atenção com a quantidade de loops feitos, pois diversos loops encadeados podem fazer você não passar em alguns dos testes feitos (normalmente passará nos mais simples, contudo não conseguirá a pontuação completa).
Segundo vim trazer mais um assunto possível para a prova, o qual explicarei posteriormente na aula sobre grafos, no entanto colocarei um exemplo de fácil entendimento da seção pratique da OBI, do nível 2, Batuíra (código resolvido abaixo):
#include
#define INF 1000000;
int main()
{
/* Batuíra */
int num = 1; /* Número do teste */
int n, x, y, z; /* Quantidade de pontos e variáveis para distância */
int dist[110][110]; /* Grafo para distância dos pontos */
int i, j, k; /* Contadores para loop for */
/* O Grafo dist[110][110] representa as distâncias entre os pontos de
repouso. Por exemplo, o valor de dist[i][j] é a distância entre os pontos
i e j */
/* Entrada do número de pontos */
scanf (“%d”, &n);
while (n != 0)
{
/* Coloca a distância padrão entre os pontos */
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (i == j)
{
dist[i][j] = 0; /* A distância para o próprio
ponto de repouso é zero */
}
else
{
dist[i][j] = INF; /* Diz que a distância entre os pontos
é “infinita”, ou seja, não há ligação entre eles */
}
}
}
/* Lê os pontos e a distância entre eles */
scanf (“%d %d %d”, &x, &y, &z);
/* A distância do ponto x ao ponto y é igual a z */
while (x != 0) /* Quando qualquer valor for zero é o fim da
entrada dos pontos */
{
/* Coloca as distâncias nas duas direções */
dist[x][y] = z;
dist[y][x] = z;
/* Lê os pontos e a distância entre eles */
scanf (“%d %d %d”, &x, &y, &z);
}
/* Algoritmo de Floyd-Warshall */
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
/* Se houver um ponto de repouso entre i e j com uma
menor distância, então o valor de pontos[i][j] é
substituído pelo de (dist[i][k] + dist[k][j]) */
if ((dist[i][k] + dist[k][j]) < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
dist[j][i] = dist[i][k] + dist[k][j];
}
}
}
}
/* Depois desse laço principal o valor de dist[1][n] é a menor
distância entre o ponto inicial e o final, a qual representa o valor
pedido pelo problema */
/* Saída de dados */
printf (“Teste %d\n%d\n\n”, num, dist[1][n]);
/* Incremento para o próximo caso de teste */
num++;
/* Entrada para o próximo caso de teste */
scanf (“%d”, &n);
}
return (0);
}
Fiquem bem atentos a parte de grafo, além do famoso algoritmo de Floyd-Warshall, o qual é suficientemente eficiente para esse problema.
Serão colocados comentários com dicas para os problemas “The Trip”, em Exercícios 1 (Parte I) e “Jolly Jumpers”, na Aula 2, pois foram resolvidos por mim no site do UVa Online Judge (finalmente).
Por fim, boa sorte a todos os que irão participar da competição amanhã (OBI), tomara que seja uma boa prova! Eu também participarei, esperando um bom resultado, se Deus quiser.
Posts interessantes:
- Programando melhor: Aula 4 – Ordenação
- OBI vem aí!
- Programando melhor: Aula 3 – Strings
- Programando melhor: Aula 1 – Começando
E você, como se preparou para a OBI? Ah, quando a prova terminar, postem suas opiniões aqui e vamos discutir as questões! Comentem!
Helton de Melo Duarte
“Entrega o teu caminho ao Senhor, confia nEle e Ele tudo fará.” Salmos 37.5
“O meu escudo está com Deus, que salva os retos de coração.” Salmos 7.10
Programando melhor: Exercícios 1 (Parte I)
Agora é a hora da diversão!!!
Bem pessoal, como prometido, chegou hoje a primeira bateria de exercícios do nosso curso “Programando melhor”, para você que deseja se tornar um melhor programador/competidor. Além disso, venho compartilhar com vocês a enorme vantagem nesse tipo de competição de quem domina bem a matemática (em competições também), pois hoje tive mais uma aula do Programa de Iniciação Científica OBMEP 2007 e fiquei ainda mais amando essa matéria (o que me faz gostar cada vez mais de programação pesada!). Mas vamos pôr a mão na massa!
Problema 1: The 3n+1 Problem (O problema do 3n+1)
UVa ID (código no site da Universidad de Valadollid): 100 ; Nível: Fácil
Considere o seguinte algoritmo para gerar uma sequência de números. Comece com um inteiro n. Se n é par, divida por 2. Se n é ímpar, multipique por 3 e some 1. Repita esse processo com o novo valor de n, terminando quando n = 1. Por exemplo, a seguinte sequência de números será gerada a partir de n = 22.
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
É conjecturado (mas ainda não provado) que esse algoritmo terminará em n=1 para qualquer inteiro n. Ainda, a conjectura assegura para todos os inteiros até 1 milhão.
Para uma entrada n, o tamanho do ciclo de n é o número de números gerados, incluindo o 1. No exemplo acima, o tamanho do ciclo de 22 é 16. Dados qualquer dois números i e j, você deve determinar o maior tamanho do ciclo dentre todos os inteirosdf entre i e j, incluindo ambos os extremos.
Entrada
A entrada consistirá numa série de pares de inteiros i e j, um par de inteiros por linha. Todos os inteiros serão menores do que 1 milhão e maiores que 0.
Saída
Para cada par de inteiros i e j, coloque i e j na mesma ordem que eles apareceram na entrada e então o maior tamanho de ciclo para todos os inteiros entre e incluindo i e j. Esses três números devem estar separados por um espaço, com todos os três números em uma linha e com uma linha de saída para cada linha de entrada.
Exemplo de entrada/saída
Entrada -> 1 10 ; Saída -> 1 10 20
Entrada -> 100 200 ; Saída -> 100 200 125
Entrada -> 201 210; Saída ->201 210 89
Entrada -> 900 1000 ; Saída -> 900 1000 174
Problema 2: The Trip (A Viagem)
UVa ID: 10137 ; Nível: Fácil
Um grupo de estudantes são membros de um clube que viaja anualmente para diferente locais. Os destinos deles no passado incluem Indianapolis, Phoenix, Nashville, Philadelphia, San Jose e Atlanta. Essa primavera eles estão planejando uma viagem para Eindhoven.
O grupo concorda a princípio compartilhar as despesas igualmente, mas não é prático compartilhar cada despesa no momento em que ela ocorre. Então indivíduos no grupo pagam por certas coisas, como refeições, hotéis, táxi e passagens aéreas. Depois da viagem, as despesas de cada estudante são contadas e o dinheiro é trocado para que o custo líquido para cada um seja o mesmo, para cada centavo. No passado, esse dinheiro trocado foi tedioso e consumiu muito tempo. Seu trabalho é computar, de uma lista de despesas, a quantia mínima de dinheiro que deve trocar de mãos em virtude de igualar (com diferença máxima de 1 centavo) todos os custos dos estudantes.
Entrada
A entrada padrão irá conter a informação para diversas viagens. Cada viagem consiste de uma linha contendo um inteiro positivo n, o qual representa o número de estudantes na viagem. Isso é seguido por n linhas de entrada, cada uma contendo a quantia gasta pelo estudante em dólares e centavos. Não há mais do que 100 estudantes e os estudantes não irão gastar mais do que $10.000,00 cada. Uma linha contendo 0 segue a informação da última viagem.
Saída
Para cada viagem, forneça uma linha de saída informando a quantia total de dinheiro, em dólares e centavos, que deve ser trocada para igualar os custos dos estudantes.
Exemplo de entrada
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
Exemplo de saída (correspondente à entrada acima)
$10.00
$11.99
Bem pessoal, agora mesmo irei colocar a Parte II desses exercícios, com mais um do nível Fácil e outro do nível Médio, ok? Fiquem à vontade para perguntar e, com certeza, dar dicas para a resolução dos problemas. Soluções completas dos problemas não serão aceitas em comentários, pois (após discutir com algumas pessoas) seria algo que tiraria a “graça” dos problemas propostos, porém qualquer dica a respeito é bem-vinda! Além disso, eu mesmo irei postar as minhas dicas quando eu pegar esses problemas pra valer (amanhã), blz?
Posts interessantes:
- Programando melhor: Exercícios 1 (Parte II)
- Programando melhor: Aula 1 – Começando
- Cursos grátis na Internet – MIT
- Top Coder Marathon Matches
- Olimpíadas do Conhecimento
Helton de Melo Duarte
“A sabedoria é a coisa principal: adquire, pois, a sabedoria; sim, com tudo o que possuis adquire o entendimento. Estima-a e ela te exaltará; se a abraçares, ela te honrará. Ela dará à tua cabeça uma grinalda de graça; e uma coroa de glória te entregará.” (Provérbios 4.7-9)
