TRABALHO FINAL DE ESTRUTURA DE DADOS

Prévia do material em texto

TRABALHO FINAL DE ESTRUTURA DE DADOS - ESTÁCIO/CEUT
Valor do trabalho: 10,0
Forma de execução: em duplas, no máximo
Data final para entrega: 14/11/2017
Forma de apresentação: código fonte + executável a ser apresentada ao professor
1) IDENTIFICADOR DE ESTRUTURA DE DADOS
Existe uma estrutura de dados genérica, do tipo sacola, suportando duas operações:
1 x Jogue um elemento x na sacola.
2 Tire um elemento da sacola.
Dada uma sequencia de operações que retornam valores, você deverá identificar a
estrutura de dados. É uma pilha (LIFO), uma fila (FIFO), uma fila de prioridade (sempre
tire os elementos grandes primeiro) ou qualquer outra estrutura que você dificilmente
consegue identificar! Você deverá utilizar conceitos de manipulação de arquivos de
texto, que configuram a fonte de entrada.
ENTRADA
Existem muitos casos de testes. Cada caso de teste começa com a linha contando um
único inteiro n (1 <= n <= 1000). Cada uma das seguintes n linhas é um comando do tipo
1, ou um número inteiro 2, seguido de um número inteiro x. Isso significa que depois de
executar um comando do tipo 2, obtemos um elemento x sem erros. O valor de x é
sempre um número inteiro, positivo e não maior do que 100. O final da entrada é
determinado pelo final do arquivo (EOF). O tamanho do arquivo de entrada não deve
exceder 1MB.
Saída
Para cada caso de teste, mostre um dos seguintes:
stack
É uma pilha.
queue
É uma fila.
priority queue
É uma fila de prioridade.
impossible
Não pode ser nem uma pilha, nem uma fila nem uma fila de prioridade.
not sure
Pode ser mais de uma das três estruturas mencionadas acima.
Exemplo:
2) BRINDE FACE 2015
A FACE em 2015 está apoiando a terceira edição da Maratona de Programação, mas
desta vez a organização solicitou sua ajuda para criar um sistema de sorteio utilizando
as letras da palavra FACE. Como a feira utiliza uma proposta diferenciada e alegre, cada
participante que entra na feira ganha 4 letras, uma de cada cor e em formato de bloco
de madeira, conforme Figura 1, e deve inseri-las num painel. Se, no momento da
inserção, as 4 letras formarem o contrário das 4 últimas letras, o visitante ganhará um
brinde.
Figura 1 - Entrada de FACE no painel seguido de ACEF.
Por exemplo: suponha que já tiveram 3 participantes que entraram na feira e o painel
ficou da seguinte forma: F A C E E C F A A C F E A C E F. Note que sempre que o painel
fica vazio, assim como no início do evento, as letras F A C E são inseridas pela
organização do evento. Agora, na entrada do quarto participante, ele inseriu as letras F
E C A e, com isso, receberá um brinde por fechar o contrário de A C E F. Após essa
situação, o painel deve ficar F A C E E C F A A C F E.
Escreva um algoritmo que, dadas as letras recebidas e inseridas pelos participantes,
diga quantos participantes ganharam brindes. Lembre-se que sempre que o painel fica
vazio as letras F A C E são inseridas pela organização do evento.
Entrada
A primeira linha de cada caso de teste contém um inteiro N (1 ≤ N ≤ 100),
representando o número de visitantes que vão receber as letras. Em cada uma das N
linhas seguintes deve ser informada a combinação das 4 letras que o visitante deseja
inserir no painel, separadas por espaço.
Saída
Para cada grupo de visitantes, deve ser informado quantos destes receberão brindes.
3) FILA DE SUPERMERCADO
Hoje é a inauguração do supermercado Matheus em Teresina, e todos estão muito
excitados com os baixos preços prometidos.
Este supermercado tem N funcionários que trabalham no caixa, identificados por
números de 1 a N, onde cada funcionário leva um determinado tempo vi para processar
um item de um cliente. Ou seja, se um cliente tem cj itens em sua cesta, um
determinado funcionário levará vi*cj segundos para processar todos os itens deste
cliente.
Quando um cliente entra na fila para ser atendido ele espera até que um funcionário
esteja livre para atendê-lo. Se mais de um funcionário estiverem livres ao mesmo tempo,
o cliente será atendido pelo funcionário de menor número de identificação. Tal
funcionário só estará livre novamente após processar todos os itens deste cliente.
Há M clientes na fila para serem atendidos, cada um com um determinado número de
itens na sua cesta. Dadas as informações sobre os funcionários nos caixas e os clientes,
o gerente pediu sua ajuda para descobrir quanto tempo levará para que todos os
clientes sejam atendidos.
Entrada
A primeira linha conterá dois inteiros N e M, indicando o número de funcionários no
caixa e o número de clientes, respectivamente (1 ≤ N ≤ M ≤ 104).
Em seguida haverá N inteiros vi, indicando quanto tempo leva para o i-ésimo funcionário
processar um item (1 ≤ vi ≤ 100, para todo 1 ≤ i ≤ N).
Em seguida haverá M inteiros cj, indicando quantos itens o j-ésimo cliente tem em sua
cesta (1 ≤ cj ≤ 100, para todo 1 ≤ j ≤ M).
Saída
Imprima uma linha contendo um inteiro, indicando quanto tempo levará para que todos
os clientes sejam atendidos.
4) FILA DO SUS
Os pacientes que chegam na fila do SUS passam por uma triagem imediatamente e vão
para a fila de atendimento. Na triagem a enfermeira anota o horário de entrada do
paciente e quantos minutos ele tem até que sua condição de saúde se torne crítica.
Sabe-se que os pacientes são atendidos de 30 em 30 minutos (sempre nas horas cheias
ou meias horas) quando na fila de atendimento. O inicio da triagem e do atendimento se
dá às 7h da manhã, se não há nenhum paciente sendo atendido e a fila está vazia, o
primeiro paciente é atendido no instante que chega na triagem. O médico atende até o
último paciente na fila. A preocupação é se algum paciente atingiu uma condição crítica
enquanto não tenha sido atendido. Para tanto você foi convidado para verificar na fila
quantos pacientes atingem a condição crítica.
Entrada
A entrada contém vários casos de teste. Cada caso de teste começa com uma linha
com o número inteiro N, 0 < N < 25; o número de pacientes que chegam à triagem. A
seguir são N linhas com os valores inteiros H, M e C, com 7 < H < 19, e 0 ≤ M <60, a
hora e minuto que o paciente chega à triagem. O paciente da linha i sempre chega antes
que, e no máximo junto com, o paciente da linha i + 1. E 0 ≤C ≤ 720 o número de
minutos antes do paciente atingir a condição crítica de saúde.
Saída
Para cada caso de teste pede-se que se imprima em uma linha única o número de
pacientes que atingiram a condição crítica ainda na fila de atendimento.
	ENTRADA
	Saída