Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1802 | [P1]
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1802
Books Catalog
By Thalyson Nepomuceno, Universidade Estadual do Ceará 
Brazil
Timelimit: 2
Bino is preparing a book catalog. He is organizing a catalog with K different sets of books to sell in your online store. Each set of books consists of five books, one for each subject (portuguese, mathematics, physics, chemistry and biology). Two sets of books are considered distinct if there is at least one book that is at one and the other is not. Bino want to expose on the site only the most expensive distinct sets, and asked for your help.
The value of each set is the sum of the values of each book that's in it. Your task is to calculate the total value of K more expensive distinct sets of books. In case of a draw among the most expensive sets, Bino choose any more expensive set.
Input
The input consists of 6 lines: The first line contains an integer P (5 ≤ P ≤ 10), representing that Bino has P different types of portuguese books, followed by P integers vi (1 ≤ vi ≤ 1000), representing the values of each Portuguese book. The second line contains an integer M (5 ≤ M ≤ 10), representing that Bino has M different types of math books, M integers vi (1 ≤ vi ≤ 1000), representing the values of each math book. The third line contains an integers F (5 ≤ F ≤ 10), representing that Bino has F different types of physics books, followed by F integers vi (1 ≤ vi ≤ 1000) representing the values of each physics book. The fourth line contains an integer Q (5 ≤ Q ≤ 10) representing that Bino has Q different types of chemistry books, followed by Q integers vi (1 ≤ vi ≤ 1000) representing the values of each chemistry book. The fifth line contains an integer B (5 ≤ B ≤ 10), representing that Bino has B different types of biology books, followed by B integers vi (1 ≤ vi ≤ 1000) representing the values of each biology book. The sixth line contains an integer K (1 ≤ K ≤ M*P*Q*F*B) representing the amount of different sets of books in books catalog.
Output
Print the sum of K more expensive distinct sets of books.
| Input Sample | Output Sample |
|
5 2 5 6 3 8 |
42 |
| Input Sample | Output Sample |
|
5 2 5 6 3 8 |
397 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
int main()
{
ios::sync_with_stdio(false);
int b[5], x;
vector < vector<int>> books(5);
for (int i = 0; i < 5; i++) {
cin >> b[i];
for (int j = 0; j < b[i]; j++) {
cin >> x;
books[i].pb(x);
}
}
vector<int> results;
for (int i = 0; i < b[0]; i++) {
for (int j = 0; j < b[1]; j++) {
for (int k = 0; k < b[2]; k++) {
for (int l = 0; l < b[3]; l++) {
for (int m = 0; m < b[4]; m++) {
results.pb(books[0][i] + books[1][j] + books[2][k] + books[3][l] + books[4][m]);
}
}
}
}
}
sort(results.begin(), results.end(), greater < int>());
cin >> x;
int resp = 0;
for (int i = 0; i < x && i < results.size(); i++)
resp += results[i];
cout << resp << endl;
return 0;
}
Input
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
Output
#2 Code Example with Python Programming
Code -
Python Programming
por = [int(x) for x in input().split()][1:]
mat = [int(x) for x in input().split()][1:]
qui = [int(x) for x in input().split()][1:]
fis = [int(x) for x in input().split()][1:]
bio = [int(x) for x in input().split()][1:]
k = int(input())
v = set()
for a in por:
for b in mat:
for c in qui:
for d in fis:
for e in bio: v.add(tuple([a, b, c, d, e]))
print(sum(sorted([sum(i) for i in v], reverse=True)[:k]))
Input
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
Output