P1460 [USACO2.1] Healthy Holsteins

Farmer John prides himself on having the healthiest cows in the world. He knows the minimum amount of each vitamin that the cows need from different feeds. Please help him feed his cows to keep them healthy while minimizing the number of feed types used. Given the cows’ minimum vitamin requirements, output which types of feed to use so that the total number of feeds is minimized. Vitamin amounts are integers. Each type of feed can be used at most once. It is guaranteed that a solution exists.

The first line contains an integer $v$, the number of vitamin types required. The second line contains $v$ integers, the minimum daily amount required for each vitamin. The third line contains an integer $g$, the number of available feed types. Each of the next $g$ lines contains $v$ integers; the $n$-th of these lines gives the amounts of each vitamin contained in feed number $n$.

Output a single line containing the minimum number of feed types $p$, followed by $p$ integers: the chosen feed indices in increasing order. If there are multiple solutions, output the one with the smallest sequence of feed indices (i.e., lexicographically smallest).

Constraints For $100\%$ of the testdata, $1\le v \le 25$, $1\le g \le 15$. All integers in the input are in the range $[1,1000]$. USACO 2.1 Translation from NOCOW. Translated by ChatGPT 5