P2744 [USACO5.3] Milk Measuring

Farmer John wants to measure $Q$ (1 ≤ Q ≤ 20,000) quarts of his finest milk and put it into a large bottle to sell. He always gives exactly what the customer wants, without any error. Farmer John is very frugal. He is now buying some buckets at the cow hardware store to measure out $Q$ quarts from his huge pool of milk. Each bucket costs the same. Your task is to compute the smallest set of buckets he can buy such that, using only these buckets, he can measure exactly $Q$ quarts. Additionally, because he must carry them home, among two minimal bucket sets, he chooses the “smaller” one: sort both sets in ascending order, compare the first bucket; choose the set whose first bucket has the smaller capacity. If the first bucket is equal, compare the second, and so on, until they differ. For example, the set $\{3,5,7,100\}$ is better than the set $\{3,6,7,8\}$. To measure the milk, Farmer John may fill a bucket from the pool and pour it into the bottle. He never pours milk out of the bottle, nor does he pour a bucket’s milk anywhere else. With a $1$-quart bucket, Farmer John can measure all possible numbers of quarts using only that bucket. Other bucket combinations are not so convenient. Compute the best set of buckets to purchase. It is guaranteed that all testdata have at least one solution.

The first line contains an integer $Q$. The second line contains an integer $P$ (1 ≤ P ≤ 100), the number of buckets available in the store. Lines $3$ through $P+2$ each contain an integer $h_i$ representing the capacity of the $i$-th bucket. $(1\le h_i\le 10^4)$.

Output exactly one line of space-separated integers: First, the minimum number of buckets needed to measure the desired number of quarts, followed by: a sorted list (in increasing order) of the capacities of the buckets to purchase.

Translation source: NOCOW. USACO Training Section 5.3. Translated by ChatGPT 5