P2729 [USACO3.2] Feed Ratios

Farmer John always feeds his cows with the best-mixed feed. The feed is blended from three ingredients: barley, oats, and wheat. He knows the exact ratio of his ideal feed, but such a feed is not available on the market. He has to purchase three other mixed feeds (each also composed of the same three grains) and blend them to produce his perfect feed.

Given three sets of integers, each set represents the ratio of barley, oats, and wheat in one feed. Find a way to blend these three feeds to obtain a feed with ratio $x:y:z$. Write a program to find the solution that minimizes the total amount of the three feeds used. If it is impossible to obtain the target feed from these three feeds, output a single line containing the string `NONE`. “Minimum amount” means the sum of the amounts (integers) of the three feeds must be minimized. For example, if we want to use feeds with ratios $1:2:3$, $3:7:1$, and $2:1:2$ to produce a feed with ratio $3:4:5$, we can blend $8$ units of the first feed, $1$ unit of the second feed, and $5$ units of the third feed to obtain $7$ units of the target feed. This is because $8 \times 1 + 1 \times 3 + 5 \times 2 = 21$, $8 \times 2 + 1 \times 7 + 5 \times 1 = 28$, $8 \times 3 + 1 \times 1 + 5 \times 2 = 35$, and $21:28:35$ is exactly equal to $3:4:5$.

The first line contains three integers $x, y, z$, indicating that the target feed has barley, oats, and wheat in the ratio $x:y:z$. The next three lines, the $i$-th line contains three integers $a_i, b_i, c_i$, indicating that the $i$-th feed has barley, oats, and wheat in the ratio $a_i:b_i:c_i$. All integers in the input are between $0$ and $99$ inclusive, and in each line the three integers are not all $0$.

If the target feed can be obtained by blending the three feeds, output one line with $4$ integers. The first three integers $m, n, p$ represent the portions of the three feeds, and the fourth integer represents the number of portions of the target feed obtained. If there are multiple solutions, output the one with the smallest $m+n+p$. If the target feed cannot be obtained from the three feeds, output a single line containing the string `NONE`. It is guaranteed that if a solution exists, the solution with the smallest $m+n+p$ is unique.

Translation from NOCOW. USACO Training Section 3.2. Translated by ChatGPT 5