# UVa 11088

## Summary

You're trying to make the most groups of threes as possible. Since ${\displaystyle N\leq 15}$, this is a time for Dynamic Programming, as there are only ${\displaystyle N^{3}}$ subproblems.

## Explanation

Using Dynamic Programming, we can solve the problem with its subproblem as such:

${\displaystyle best(S)=0{\mbox{ where }}|S|<3}$

${\displaystyle best(S=\{a_{1},a_{2},a_{3},\ldots ,a_{n}\})=\max _{i,j,k}\left(best(S-a_{i}-a_{j}-a_{k})+{\begin{cases}1,&{\mbox{if }}a_{i}+a_{j}+a_{k}\geq 20\\0,&{\mbox{otherwise}}\end{cases}}\right)}$

Basically, what this is saying is, if the current subproblem has less than 3 people, it can't form a team, so it will give the answer 0. Otherwise, take the max ${\displaystyle i,j,k}$ such that it yields the best results from the rest that weren't used. Since there are at most ${\displaystyle O(2^{N})}$ subproblems, saving the results down is good enough.

## Optimizations

The naive implementation is ${\displaystyle O(N^{3}2^{N})}$. There's an ${\displaystyle O(N^{2}2^{N})}$ solution which takes advantages of the fact that you should always include the "biggest" element in the set in the next step.

## Input

9
22 20 9 10 19 30 2 4 16
2
15 3
0


## Output

Case 1: 3
Case 2: 0


## Implementation

/*
Problem: 11088 - End up with More Teams
(http://blogaritmo.factorcomun.org)

Accepted
*/

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

#define bit(i, n) (n & (1 << i))

int memo[1<<15], x[15], n;

/*
Returns the maximum amount of teams that can be made using
teams set on on bitwise mask avail. At each step, I try to
build a new team using the first available person, or igno-
re that person completely.
*/
int best(int avail){
int &ans = memo[avail];
if (ans == -1){
ans = 0;
for (int i=0; i<n; ++i)
if (bit(i, avail)){
ans = max(ans, best(avail & ~(1 << i))); //Ignore this dogg
for (int j=i+1; j<n; ++j)
if (bit(j, avail))
for (int k=j+1; k<n; ++k)
if (bit(k, avail))
if(x[i] + x[j] + x[k] >= 20)
ans = max(ans, 1 + best(avail & ~(1 << i) & ~(1 << j) & ~(1 << k))); //Make team (i, j, k).
break;
}
}
return ans;
}

int main(){
int pizza = 1;
while (scanf("%d", &n) == 1 && n){
for (int i = 0; i<n; ++i) scanf("%d", &x[i]);

memset(memo, -1, sizeof memo);
printf("Case %d: %d\n", pizza++, best((1 << n) - 1));
}

return 0;
}