Blog de Helton Duarte

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

This entry was posted on sexta-feira, março 27th, 2009 at 22:02 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.