Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2029
The prestigious ICPC is here again. The coaches are busy selecting teams. Well this year, they have adopted a new policy. Contrary to traditional selection process, where few individual contests are held and the top three are placed in one team the next three in another and so on, this year the coaches decided to place members in such a way that the total number of promising teams is maximized. Promising teams are defined as a team having ability points of its members adding up to 20 or greater. Here ability point of a member denotes his capability as a programmer, the higher the better. Input There will be as many as 100 cases in the input file. Each case of input has two lines. The first line contains a positive integer, where n indicates the number contestants available for selection. The next line will contain n positive integers, each of which will be at most 30. End of input is indicated by a value of 0 for n. Output For every case of input there will be one line of output. This line should contain the case number followed by the maximum number of promising teams that can be formed. Note that it is not mandatory to assign everyone in a team. Incase you dont know, each team consists of exactly 3 members. Constraints • n ≤ 15
Sample Input 9 22 20 9 10 19 30 2 4 16 2 15 3 0
Sample Output Case 1: 3 Case 2: 0
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
vector<int> memo;
vector<int> ppl;
int solve(int bitmask){
if(memo[bitmask]!=-1) return memo[bitmask];
int best = 0;
for(int i=0;i<ppl.size();i++){
if(bitmask & (1<<i)) continue;
for(int j=i+1;j<ppl.size();j++){
if(bitmask & (1<<j)) continue;
for(int k=j+1;k<ppl.size();k++){
if(bitmask & (1<<k)) continue;
int sum = ppl[i]+ppl[j]+ppl[k];
if(sum <20) continue;
int next_bitmask = bitmask | (1<<i) | (1<<j) | (1<<k);
best = max(best, 1+solve(next_bitmask));
}
}
}
return memo[bitmask] = best;
}
int main() {
int tc=1,n,v;
while(scanf("%d",&n),n){
memo.assign(1<<n,-1);
ppl.clear();
for(int i=0;i<n;i++){
scanf("%d",&v);
ppl.push_back(v);
}
printf("Case %d: %d\n",tc++, solve(0));
}
}Input
22 20 9 10 19 30 2 4 16
2
15 3
0
Output
Case 2: 0
Demonstration
UVA Online Judge solution -11088 - End up with More Teams - UVA Online Judge solution in C,C++,java