18 lines
2.2 KiB
TeX
18 lines
2.2 KiB
TeX
O sistema de entregas automáticas da cidade de Logitown é composto por um anel de estações interligadas. Em cada estação, pequenas encomendas aguardam para serem levadas até seus destinos, que também são outras estações do mesmo anel.
|
|
|
|
Um único carrinho autônomo é responsável por realizar todas as entregas. Ele percorre continuamente as estações em ordem crescente: após visitar a estação $N$, retorna para a estação $1$, repetindo o ciclo até que todas as encomendas tenham sido entregues. No início da operação, o carrinho está vazio e parado na estação $1$.
|
|
|
|
Cada estação possui duas plataformas de operação:
|
|
\begin{itemize}
|
|
\item \textbf{Plataforma A}: recebe as encomendas que chegaram ao seu destino final.
|
|
\item \textbf{Plataforma B}: mantém uma fila de encomendas que ainda precisam ser enviadas para outras estações.
|
|
\end{itemize}
|
|
|
|
O carrinho possui uma pilha interna com capacidade limitada, utilizada para armazenar as encomendas em trânsito. Como se trata de uma pilha, apenas a encomenda localizada no topo pode ser retirada. Ao chegar a uma estação, o carrinho inicia o processo de \textbf{descarregamento}, retirando do topo da pilha as encomendas uma a uma. Cada encomenda é depositada na plataforma A da estação caso seu destino corresponda à estação atual; caso contrário, o carrinho tenta colocá-la na fila da plataforma B, desde que haja espaço disponível. Se a fila estiver cheia e o destino da encomenda no topo da pilha não corresponder à estação atual, o processo de descarregamento é interrompido.
|
|
|
|
Em seguida, ocorre o \textbf{carregamento}: o carrinho pega, na ordem da fila da plataforma B, as encomendas que aguardam envio e as adiciona ao topo da pilha, até que esta atinja sua capacidade máxima ou a fila fique vazia.
|
|
|
|
Cada operação de carregamento ou descarregamento de uma encomenda leva exatamente $1$ minuto, enquanto o deslocamento entre duas estações consecutivas consome $2$ minutos. O processo continua até que não restem encomendas no carrinho nem em nenhuma das plataformas B.
|
|
|
|
Dado o estado inicial das plataformas, determine o tempo total necessário para que todas as encomendas sejam entregues às suas respectivas estações.
|