Prazo de entrega recomendado:
Vamos resolver alguns problemas do cotidiano de um certo laboratório de pesquisa. Enquanto não é difícil escrever algoritmos que respeitem as restrições de cada problema, nesta tarefa iremos perceber que, mesmo para problemas corriqueiros, precisamos estudar e escrever algoritmos eficientes.
1. Compras do laboratório
Maria é a pesquisadora responsável por organizar e comprar os equipamentos de seu laboratório de P&D. Os membros do laboratório mandam suas requisições, que são colocadas em uma lista de demandas, em que um mesmo item pode ser pedido por vários pesquisadores. Maria então consulta possíveis fornecedores para atender os pedidos de seus colegas.
Um fornecedor responde com uma lista de itens disponíveis, incluindo
repetições. Seu objetivo é descobrir quais itens demandados Maria não
pode comprar de um dado fornecedor. Escreva seu programa em um arquivo
compras.py.
Atenção: nesta questão, não utilize as estruturas de dados set e
dict, apenas list. Também estão proibidas as features que deixam o
algoritmo implícito, como o operador de pertinência in. A sintaxe
for x in X pode ser usada livremente. Qualquer dúvida, pergunte no
canal da tarefa.
Entrada
Cada equipamento é representado por um número inteiro. A entrada é formada por duas linhas contendo as listas de números representando os itens demandados e os itens disponíveis.
5 9 2 5 3 2 1 1 9
1 5 4 3 3 7 4 7 8 2 2
Saída
A saída contém a lista de itens que não podem ser comprados, em ordem crescente.
1 5 9 9
2. Cadeias fortes
O laboratório em que Maria trabalha pesquisa a criação de materiais super resistentes nunca vistos antes! Esses materiais hipotéticos são formados ligando pares de novos tipos de moléculas sintéticas — e super-secretas. Nem todas as moléculas podem ser ligadas, então Maria utiliza uma máquina — mais secreta ainda — que é capaz de identificar que pares de moléculas se ligam.
Os levantamentos preliminares dão indícios de que as qualidades inigualáveis dos materiais estudados são decorrentes da presença de cadeias fortes em sua composição. Uma cadeia forte é um trio de moléculas em que todas podem ser ligadas entre si, par a par. A figura abaixo mostra as conexões das moléculas 1, 2, 3, 5 e 99, onde estão presentes as cadeias fortes 1, 2 e 3, e a 2, 3 e 99.
A máquina de Maria só consegue analisar dois tipos de moléculas por
vez, então a identificação de cadeias fortes precisa ser feita
implicitamente a partir dos pares de moléculas conectáveis. Como o
número de moléculas é muito grande, você foi contratado para
automatizar essa tarefa. Crie um programa cadeias.py que, dados os
pares de moléculas conectadas, liste todas as cadeias fortes.
Atenção: nesta questão está liberado o uso de todas as estruturas de dados vistas em aula.
Entrada
Cada tipo de molécula é representado por um número inteiro. A entrada
é formada por um inteiro m na primeira linha, representando o número
de pares de moléculas conectadas, seguido por m linhas que descrevem
os pares, formados por números inteiros.
6
1 3
99 5
3 99
1 2
2 3
2 99
Saída
A saída contém uma lista de todas cadeias fortes em ordem
lexicográfica. Cada cadeia forte é representada por uma linha a b c
com $a < b < c$.
1 2 3
2 3 99
Dica
Existem muitos algoritmos diferentes que resolvem este problema. Uma
primeira ideia é enumerar os trios de pares de moléculas conectadas e,
em seguida, testar se uma cadeia forte é formada. Isso pode ser feito
com três comandos for aninhados, percorrendo a lista que guarda os
pares de moléculas. Saiba que apenas esse algoritmo não é capaz de
resolver os casos de teste maiores: explore as estruturas de dados
vistas em aula para obter um algoritmo mais eficiente!
Correção
Depois de submetida e terminada a tarefa, você deverá apresentá-la a
um monitor PED. Para isso, você deve procurar atendimento em algum
horário com monitor PED e digitar apresentar 9 no canal
fila-apresentar.
Em cada problema, temos casos de teste pequenos, médios e grandes. Para obter o conceito C, você precisa resolver os casos de teste pequeno e médio do primeiro problema, além dos casos de teste pequenos do segundo problema. O conceito B é obtido ao resolver também os casos de teste médios do segundo problema. O conceito A é dado ao resolver todos os casos de teste.
Lembre-se de que seu programa deverá estar organizado em funções adequadamente, cada uma com uma responsabilidade bem definida. Crie uma função principal e não execute instruções no nível global. Não serão aceitos programas desorganizados ou ilegíveis. Procure adicionar comentários objetivos para documentar as funções e explicando o que fazem trechos de código mais complicados.
A pasta da tarefa no seu repositório vem inicialmente com um arquivo
nao_corrigir.txt que serve para indicar que você ainda está
trabalhando nesta tarefa. Você pode realizar quantos pushes quanto
forem necessários. O monitor só irá corrigir sua tarefa quando esse
arquivo for removido do repositório.