1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
/*
ID: mytbk921
LANG: C
TASK: holstein
*/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int vitamins[25];
int feeds[15][25];
int nv;
int nf;
static unsigned
popcount(unsigned x)
{
unsigned c = 0;
while (x) {
if (x&1) c++;
x >>= 1;
}
return c;
}
int main()
{
FILE *fin = fopen("holstein.in", "r");
FILE *fout = fopen("holstein.out", "w");
int i, j;
unsigned scm, best, ans_n, tn;
int tmp_v[25];
fscanf(fin, "%d", &nv);
for (i=0; i<nv; i++)
fscanf(fin, "%d", &vitamins[i]);
fscanf(fin, "%d", &nf);
for (j=0; j<nf; j++) {
for (i=0; i<nv; i++)
fscanf(fin, "%d", &feeds[j][i]);
}
/* init: use all feeds */
best = (1<<nf)-1;
ans_n = nf;
for (scm=1; scm<(1<<nf)-1; scm++) {
tn = popcount(scm);
if (tn>=ans_n)
continue;
memset(tmp_v, 0, sizeof(tmp_v));
for (i=0; i<nf; i++) {
if (scm&(1<<i)) {
for (j=0; j<nv; j++)
tmp_v[j] += feeds[i][j];
}
}
for (i=0; i<nv; i++) {
if (tmp_v[i]<vitamins[i])
break;
}
if (i==nv) {
best = scm;
ans_n = tn;
}
}
fprintf(fout, "%d", ans_n);
for (i=0; i<nf; i++) {
if (best&(1<<i))
fprintf(fout, " %d", i+1);
}
fprintf(fout, "\n");
fclose(fout);
return 0;
}
|
