#Problema Aleatório 1 - Books Catalog/Catálogo de Livros (URI)

Olá, hoje vamos discutir o do problema Catálogo de Livros, do URI.

Ps: tente resolver antes de olhar a solução!

É uma questão bastante interessante para quem está começando a programar para olimpíadas, devido ao fato de envolver elementos bastante importantes na resolução de um problema: eficiência e simplesmente parar e pensar! Mas parar e pensar? Sim! Muitas vezes os problemas não exigem nenhum conhecimento computacional avançado ou específico, apenas uma ideia/lógica correta para solucionar o problema e saber organizar/codificar essa ideia já é suficiente! (Esse assunto pode ser discutido melhor em outra oportunidade, mas para adiantar problemas desse tipo geralmente são denominados AD-HOC).

Mas vamos ao problema! O enunciado de forma resumida diz o seguinte: Bino tem vários conjuntos de diferente livros, onde cada conjunto representa uma matéria(português, matemática, física, química e biologia).  Sabendo o valor  de cada livro de uma certa matéria, sua tarefa é informar qual a soma dos valores dos K conjuntos distintos de livros mais valiosos. Onde um conjunto é definido por uma coleção de livros de cada matéria, e um conjunto é dito diferente se há pelo menos um livro diferente.

Não entendeu nada, calma! Se entendeu tudo, vamos tentar entender ainda mais com o exemplo abaixo!

A entrada de forma resumida consiste em 6 linhas, as 5 primeiras definem respectivamente a coleção de livros de português, matemática, e assim por diante. Onde o primeiro inteiro n, é a quantidade de livros dessa matéria (1 <= n <= 5). E os demais n números que o seguem, (v1,v2,v3,...vi, onde i <= n e 1 <= vi <= 1000), são os valores de cada livro nessa coleção. A sexta linha contém apenas o inteiro K. O exemplo:

5 2 5 6 3 8

5 9 6 3 1 5

5 4 8 5 2 6

5 3 2 4 9 5

5 7 8 5 1 4

1

Qual nossa resposta para esse caso? Bem nesse caso é simples, como K é igual a 1, a pergunta que temos que responder é: Qual o maior valor possível de um conjunto formado por um livro de cada matéria? Basta colocarmos no nosso conjunto os maiores elementos de cada matéria.
Utilizaríamos os elementos pintados de verde, e assim nossa resposta seria 42.


5 2 5 6 3 8
5 9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1

8 + 9 + 8 + 9 + 8 = 42.

Se K fosse 2. O conjunto em verde acima, seria o conjunto de maior valor, e o segundo conjunto de maior valor é o conjunto em amarelo abaixo, cuja soma é 41 logo a resposta é 42 + 41 = 83.

5 2 5 6 3 8

5 9 6 3 1 5
5 4 8 5 2 6
5 3 2 4 9 5
5 7 8 5 1 4
1

8 + 9 + 8 + 9 + 7 = 41.

Certo, legal! Mas então quando K > 1  teremos que escolher algum elemento para tirar e colocar outro em seu lugar? E ir fazendo isso até que tenhamos a quantidade de K pedida, depois somamos tudo? SOCORROOOOO, isso ta parecendo muito complicado de codificar!
Como organizar quais já foram utilizados? Como saber quem tirar? O WA está batendo na nossa porta!

Então, como utilizar a ideia acima de forma mais simples?
Dica 1: sempre olhe o tamanho da entrada! Na maioria das vezes é isso quem vai dizer o quão eficiente sua resposta terá que ser (podemos detalhar isso em outra oportunidade) .
Dica 2: pense!!!!!

Bem, seguindo a dica 1, perceba que n (quantidade de livros de uma certa matéria) é menor ou igual a 5. O que é bem pequeno, isso nos da a liberdade de fazer uma solução não tão eficiente sem medo de TLE. Ainda seguindo a dica 1, perceba no enunciado original da questão que "K (1 ≤ K ≤P*M*Q*F*B)". O que faz sentido já que teremos que escolher um conjunto, do tipo:

(p, m, q, f, b), onde p pertence ao conjunto de livros de português, m pertence ao conjunto de livros de matemática, ... 

Certo, agora vamos pensar! Temos que escolher um p para colocar no conjunto, quantos livros de português podemos escolher? Bem, no máximo 5 (1 <= n <= 5). E essa resposta é a mesma para os demais livros já que para todos n vai até 5. Então quantos conjuntos diferentes existem no máximo?

5*5*5*5*5 = 5⁵ = 3125. Podemos gerar essa informação que passa no tempo!

Então sabemos que podemos testar todos os conjuntos sem medo de levar TLE, então agora basta implementar isso! Como fazemos?

for p in portugues:
   for m in matematica:
      for f in fisica:
          for q in quimica:
             for b in biologia:
                 (p + m + f + q + b) é um valor de um conjunto!

Como obter a resposta final? Podemos guardar a informação anterior (em uma lista por exemplo), ordená-la, e TCHANRAAAAM a resposta será a soma dos K maiores valores!

Obrigada, espero que tenha ajudado! Segue o código se ficou alguma dúvida. 

Ps: não olhe o código sem ao menos tentar codificar sua solução!