Programação Competitiva

Aeroporto [OBI 2002]

Benjamin Grando Moreira

A crescente utilização do transporte aéreo preocupa os especialistas, que preveem que o congestionamento em aeroportos poderá se tornar um grande problema no futuro. Os números atuais já são alarmantes: relatórios oficiais demonstram que na Europa, em junho de 2001, houve uma média de 7.000 atrasos de voos por dia. Preocupada com a previsão dos seus especialistas em tráfego aéreo, a Associação de Transporte Aéreo Internacional (ATAI) está começando um estudo para descobrir quais são os aeroportos onde o tráfego aéreo pode vir a ser mais problemático no futuro.

Como programador recém contratado pela ATAI você foi encarregado de escrever um programa para determinar, a partir de uma listagem de aeroportos e voos, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento será utilizado neste estudo o número total de voos que chegam ou que partem de cada aeroporto.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém dois números inteiros A (0 ≤ A ≤ 100) e V (0 ≤ V ≤ 10000), que indicam respectivamente o número de aeroportos e o número de voos. Os aeroportos são identificados por inteiros de 1 a A. As V linhas seguintes contêm cada uma a informação de um voo, representada por um par de números inteiros positivos X e Y (1 ≤ X ≠ Y ≤ A), indicando que há um voo do aeroporto X para o aeroporto Y. O final da entrada é indicado quando A = V = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas. A primeira linha identifica o conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter o identificador do aeroporto que possui maior tráfego aéreo. Caso mais de um aeroporto possua este valor máximo, você deve listar todos estes aeroportos, em ordem crescente de identificação, e separados por pelo menos um espaço em branco. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de EntradaExemplo de Saída
5 7
1 3
2 1
3 2
3 4
4 5
3 5
2 5
3 5
1 3
1 2
3 2
1 2
2 1
0 0		Teste 1
3

 

Teste 2
1 2

 

 

 

 

 

Solução em C/C++
#include <stdio.h>
#define TAM 101
 
int main(){
 int aeroportos, voos, X, Y, infos[TAM], n = 0, i, maior;
 
 scanf("%i %i", &aeroportos, &voos);
 
 while ( aeroportos != 0 && voos != 0 ) {
  for (i=0; i <= aeroportos; i++) {
   infos[i] = 0;
  }
 
  for (i=0; i < voos; i++) {
   scanf("%i %i", &X, &Y);
   infos[X]++;
   infos[Y]++;
  }
 
  //encontra o maior
  maior = 0;
  for (i=1; i <= aeroportos; i++) {
   if (infos[i] >= maior) {
    maior = infos[i];
   }
  }
 
  n++;
  printf("Teste %i\n", n);
 
  for (i=0; i <= aeroportos; i++) {
   if (infos[i] == maior) {
    printf("%i ", i);
   }
  }
 
  printf("\n\n");
 
  scanf("%i %i", &aeroportos, &voos);
 }
 
 return 0;
}
 Teste o código: http://ideone.com/EYFZCF

Vídeo com a solução comentada

Sobre os casos de teste

O exemplo apresentado para avaliação do algoritmo é simples, mas ajuda a entender o enunciado. Na avaliação da Olimpíada Brasileira de Informática, diversos testes são feitos. O teste mais complexo envolveu 15 casos de avaliação, sendo eles com diversas situações em que mais de um aeroporto empatava no número de pousos e decolagens (teve um caso de teste em que todos os 100 aeroportos empataram e deviam ser mostrados).

Sair da versão mobile