Another brute force problem, the key to the solution is the ability to generate all possible combinations of buckets to eat: a single bucket, all pairs, all triples, and so on.
One of the easiest ways to generate all the possible combinations is to count in an integer, using the bottom N bits to represent whether the bucket is to be included in the sum or not. The bits cycle through the all the possible N combinations if one counts from 0 to 1<<N (i.e., 2N).
Here's an example where N = 3; we will count from 0 through 23-1. Buckets are numbered from right to left (backwards):
counter binary_value interpretation 0 000 Buckets included: none 1 001 Buckets included: 1 2 010 Buckets included: 2 3 011 Buckets included: 1,2 4 100 Buckets included: 3 5 101 Buckets included: 1,3 6 110 Buckets included: 2,3 7 111 Buckets included: 1,2,3
How to figure out whether a bit is switched on or not? Two pieces of knowledge are necessary: how to generate a single bit to represent bucket i and how to ask if that bit is set.
The bit for bucket i is 1<<(i-1) (1 shifted left i-1 times). The i-1 term is why folks usually number from 0 instead of 1 in many programming languages. Thus 1<<0 is 1, 1<<1 is 2, 1<<2 is 4, and so on. In fact, 1<<i is the same as 2i as long as you remain within the 32 bits of integers. Don't forget the highest bit is used to represent the sign of the number.
To ask if a bit is turned in some integer, the expression num&bit is used. The '&' operator between two integers returns a result whose bits are 1 only when the corresponding bits of its two terms are 1. Thus, 1 & 1 = 1 and 4 & 1 = 0.
This information combines to a compact little solution:
#include <stdio.h> int buckets[100]; /* bucket calories */ int B; /* # buckets */ int C; /* max calories */ int best; main () { FILE *fin = fopen ("eatpuz.in", "r"); FILE *fout = fopen ("eatpuz.out", "w"); int i, j, sum; fscanf(fin, "%d %d", &C, &B); for (i = 0; i < B; i++) fscanf(fin, "%d", &buckets[i]); for (i = 0; i < 1<<B; i++) { sum = 0; for (j = 0; j < B; j++) if (i & (1<<j)) sum += buckets[j]; if (sum > best && sum <= C) best = sum; } fprintf(fout, "%d\n", best); exit (0); }
One could also solve this problem recursively:
#include <stdio.h> int buck[24], max=0; tryb (buckets, sum) { if (sum > C) return; if (sum>max) max=sum; if (buckets > 0) { tryb (buckets-1, sum ); tryb (buckets-1, sum + buck[buckets-1]); } } int main() { FILE *f = fopen ("eatpuz.in", "r"); int i, C, B; fscanf (f, "%d%d", &C, &B); for (i=0; i<B; i++) fscanf (f, "%d", &buck[i]); fclose (f); tryb (B, 0); f = fopen("eatpuz.out", "w"); fprintf (f, "%d\n", max); fclose (f); return 0; }