[UVA] 11088 - End up with More Teams
|
I I U P C 2 0 0 6 |
|
|
Problem E: End up with More Teams |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
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 don’t know, each team consists of exactly 3 members.
|
|
|
Constraints |
|
|
- n ≤ 15
|
|
|
Sample Input |
Output for Sample Input |
|
9 |
Case 1: 3 |
|
|
|
|
Problemsetter: Shamim Hafiz |
|
題目描述：
每個隊伍三個人, 每個人都有實力值, 希望每隊的實力值總和要 >= 20, 問最多可以湊出幾隊。
題目解法：
搜索所有可能
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n, A[20];
int ret, used[20];
void dfs(int idx, int i) {
ret = max(ret, idx);
for(; i < n; i++) {
if(used[i] == 0) {
used[i] = 1;
int j, k;
for(j = i+1; j < n; j++) {
if(used[j] == 0)
for(k = j+1; k < n; k++) {
if(A[i]+A[j]+A[k] >= 20 && used[k] == 0) {
used[j] = used[k] = 1;
dfs(idx+1, i+1);
used[j] = used[k] = 0;
j = n, k = n;
}
}
}
used[i] = 0;
}
}
}
int main() {
int i, j, k, cases = 0;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
sort(A, A+n);
int m = n%3;
for(i = m, j = 0; i < n; i++)
A[j++] = A[i];
n = j, ret = 0;
memset(used, 0, sizeof(used));
dfs(0, 0);
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}