diff options
author | Iru Cai <mytbk920423@gmail.com> | 2018-04-19 23:12:23 +0800 |
---|---|---|
committer | Iru Cai <mytbk920423@gmail.com> | 2018-04-19 23:12:23 +0800 |
commit | 92d2da1251d9712ee86c733e648c0feceeb7d571 (patch) | |
tree | 9f1ea22e8ceed9bb5728e71ad3148b16cdbc8645 /2.1/holstein.c | |
parent | 8482680ad68093fa56d10364f591764250c0c2f0 (diff) | |
download | usaco-92d2da1251d9712ee86c733e648c0feceeb7d571.tar.xz |
finish 2.1
Diffstat (limited to '2.1/holstein.c')
-rw-r--r-- | 2.1/holstein.c | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/2.1/holstein.c b/2.1/holstein.c new file mode 100644 index 0000000..637a43a --- /dev/null +++ b/2.1/holstein.c @@ -0,0 +1,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; +} |