There's a Hole in the Bucket
You are likely familiar with the story of Henry and Lisa and the hole in the bucket. Not too many people know what happened after Henry managed to fix the hole in his bucket. Lisa, after the hole affair, was pretty upset with Henry. In an effort to get him to think, she had him fill a barrel with several different buckets. The barrel had to be filled exactly to the top by whole (or is that hole?) bucket quantities. Henry, being lazy (which programmers can fully understand), kept thinking about it until he could do it in the fewest buckets possible. Write a program that will output the smallest number of buckets needed to be used to fill a barrel with a given volume. The volume will never exceed 100, and the total number of buckets will not be larger than 100.
The input will have a series of test cases. For each case the first line will contain two numbers M, N; the volume of the barrel to be filled and the number of different buckets available. This line will be followed by N lines representing sizes of individual buckets. The end of file will be indicated by a barrel with zero volume.
For every case the output should be a smallest number of bucket-fulls needed to fill the barrel. If is it not possible to exactly fill the given barrel output -1.
4 2 3 1 17 4 1 2 4 5 20 3 8 5 1 0 0
2 4 4
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 24, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
I completely forgot to implement the "output -1 if..." portion and i got AC.