O serviço de alfândega está encarregado do controle dos alimentos que entraram no país e, por isso, deve fazer uma inspeção de todos os alimentos que serão trazidos. Como a quantidade de alimentos que entra é muito grande e os recursos são limitados, a alfândega deve escolher um grupo de caixas de cada lote que entra para serem inspecionadas. As caixas retiradas do lote são servidas a um programa que determinará quais delas serão inspecionadas. Se alguma dessas caixas for rejeitada, o lote todo será rejeitado.

Para escolher as caixas que serão inspecionadas, é necessário criar um sistema que faça a escolha usando um critério específico. A alfândega decidiu testar muitos critérios diferentes e você recebeu a tarefa de escolher as caixas usando a mediana estatística.

Nesse método, sempre que uma caixa é adicionada ao grupo, uma determinada caixa do grupo é selecionada para inspeção. A caixa do grupo selecionada será aquela cujo peso estiver no meio de todos os pesos do grupo, i.e., será a mediana das caixas quando elas são ordenadas por peso.

Considere que uma caixa pode ser selecionada mais de uma vez para inspeção e que, no caso do número de caixas ser par, devem ser inspecionadas as duas caixas do meio.

Crie um programa selecionar que controle o conjunto de caixas adicionadas e indique as caixas a serem inspecionadas.

Exemplo 1

Entrada

A primeira linha contém a quantidade de caixas que serão inseridas. Cada linha seguinte representa uma caixa a ser inserida, composta por uma string com até 20 caracteres que representa o nome do produto e um inteiro que representa o o peso do produto.

2
mango 2
apple 3

Saída

Para cada caixa adicionada no grupo, deverão ser impressos o nome e o peso do(s) produto(s) selecionado(s) para inspeção, conforme o exemplo abaixo.

mango: 2
mango: 2
apple: 3

Uma ilustração para esse caso é a seguinte.

Exemplo 2

Entrada

6
pear 3
orange 7
strawberry 1
blackberry 5
cucumber 8
pear 2

Saída

pear: 3
pear: 3
orange: 7
pear: 3
pear: 3
blackberry: 5
blackberry: 5
pear: 3
blackberry: 5

Critérios

É obrigatório utilizar heap para resolver a tarefa. O algoritmo para obter a mediana deve executar em tempo $O(\log n)$, em que $n$ é o tamanho do grupo.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar Próximo →