\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 323 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1998}
\end{center}

\begin{center}
{\large  Exercício-Programa 2 -- Entrega: {\bf 5 de maio}}

\vspace{0.3cm}
Simulação de Aeroporto
\end{center}

Em um aeroporto diversas pistas são utilizadas para pousos e
decolagens. O bom gerenciamento destas pistas é fundamental para o
funcionamento do mesmo. Lembrem que aviões não podem ficar circulando
indefinidamente sob risco de acabar o combustível. Quanto maior é o movimento
do aeroporto, maior a necessidade de se fazer um bom gerenciamento. Neste
exercício-programa simularemos o funcionamento de um pequeno aeroporto (com
grande movimento). 

O aeroporto tem três pistas numeradas, $1$, $2$ e $3$. As duas primeiras
pistas podem ser utilizadas para pouso ou decolagem. A pista $3$ é usada
apenas para decolagem (a menos que ocorra uma situação de emergência). 

Em cada unidade de tempo de 0 a 5 aviões chegam ao aeroporto ou comunicam à
torre o desejo de decolar. Os aviões são identificados por uma seqüência de
duas letras (identificação da companhia aérea) e três números. Além disso, os
vôos trazem um código de três letras correspondente ao aeroporto de/para onde  
vêm/vão. Ao contactar a torre, o piloto comunica, caso queira pousar, quanto
tempo de combustível ainda dispõe (de 1 a 10 unidades de tempo). Os pilotos 
que desejam decolar, qual a duração aproximada do vôo (de 1 a 50 unidades 
de tempo). Se um avião que está circulando chegar a ter tempo de combustível 0
deve pousar imediatamente. 

De tempos em tempos (probabilidade menor que 15\%) surge um vôo de emergência
(transporte de doentes, presidentes, seqüestros, etc). Estes vôos devem ter
passagem livre para decolagem ou aterrissagem, assim que se comunicam com a
torre. Cada pista pode manejar uma decolagem ou um pouso em cada unidade 
de tempo.

Os aviões que estão no ar para pousar permanecem circulando o aeroporto até
que a torre escolha e libere uma pista para o pouso (estes aviões estão em
fila única). Já para os aviões que querem decolar é designada uma das pistas,
e estes permanecem em fila até a liberação da mesma. Se um avião, entretanto,
estiver esperando a liberação da pista por mais de 10\% do tempo estimado de
vôo, ele passa a ter prioridade, e deve decolar o quanto antes (essa regra se
deve ao desejo das companhias aéreas de garantir que não haja atrasos nos seus
vôos). 
Assuma que, em cada unidade de tempo, os aviões chegando entram em filas antes
de acontecerem efetivamente decolagens ou pousos.

Você deve implementar uma estratégia que não permita que aviões caiam por
falta de combustível. Seu programa deve detectar situações críticas (4 ou mais
aviões ficarão sem combustível em um mesmo instante), e poderá escolher alguns
desses aviões problemáticos para desviar suas rotas para outros aeroportos da
região. Para isso seu programa deverá manter uma tabela de aeroportos da
região (a uma distância de até 50 unidades), e respectivas distâncias. 

Seu programa deverá ser o mais eficiente possível, e sua estratégia para
designação e liberação de pistas deverá fazer com que o tempo de espera seja
o mínimo possível. Não deverá haver duplicação de informações! Note que aviões
nas filas de decolagem estarão em duas filas ao mesmo tempo: uma fila por
ordem de chegada, e outra que marca quanto tempo resta para o tempo de espera
ultrapassar os 10\% permitidos. 

Os aviões devem ser de pelo menos 5 companhias aéreas diferentes, e os
aeroportos de origem/destino pelo menos 20. Lembrem que certas companhias
aéreas operam somente em algumas cidades. 

A simulação deverá ocorrer durante 120 unidades de tempo, mas deve ser
facilmente modificável para fazer simulações maiores. A saída de seu programa
deve indicar com clareza o que está  
acontecendo a cada momento. Mostre na tela, a cada unidade de tempo,
\begin{itemize}
\item[(a)] os conteúdos de todas as filas;
\item[(b)] o tempo médio de espera para decolagem;
\item[(c)] o tempo médio de espera para pouso;
\item[(d)] a quantidade média de combustível dos aviões esperando pouso;
\item[(d)] a quantidade média de combustível disponível nos aviões que
pousaram e
\item[(e)] a quantidade de aviões pousando/decolando em condições de
emergência. 
\end{itemize}

A saída deve ser auto-explicativa e fácil de compreender --- sem confusão.

A entrada deve ser criada por um gerador de números pseudo-aleatórios. A
simulação deverá ser facilmente modificável (número de aviões chegando, número
de pistas, etc) para que você possa fazer outros testes. Para ganhar bônus na
nota, você deve fazer uma boa saída gráfica para seu programa. Outro bônus
será dado para quem conseguir testes reais (de algum aeroporto de verdade,
como Cumbica ou Congonhas) e rodar seu sistema com eles (note que isso
implicará em ``discretizar'' seu dados). 

\end{document}
