P4026 [SHOI2008] Cyclic Debts

Alice, Bob, and Cynthia are always troubled by the messy debts among them. One day, they decide to sit together and settle everything. However, checking the authenticity of banknotes is troublesome, so they decide to exchange as little cash as possible when paying off their debts. For example, Alice owes Bob $10$ yuan, while Cynthia owes neither of them anything. Suppose Alice has one $50$ yuan note, Bob has three $10$ yuan notes and ten $1$ yuan notes, and Cynthia has three $20$ yuan notes. A straightforward way is: Alice gives the $50$ yuan to Bob, and Bob gives change back to Alice. In total, $14$ banknotes are exchanged. But this is not optimal. The optimal way is: Alice gives the $50$ to Cynthia, Cynthia gives two $20$ notes to Alice and one $20$ note to Bob, and Bob gives one $10$ note to Cynthia. In this case, only $5$ banknotes are exchanged. Before long, they find this is a hard problem, so they ask you, who are good at math, to solve it for them.

The first line contains three integers: $x_1$, $x_2$, $x_3$ ($-1,000 \le x_1, x_2, x_3 \le 1,000$), where $x_1$ is the amount Alice owes Bob (if $x_1$ is negative, it means Bob owes Alice), $x_2$ is the amount Bob owes Cynthia (if $x_2$ is negative, it means Cynthia owes Bob), $x_3$ is the amount Cynthia owes Alice (if $x_3$ is negative, it means Alice owes Cynthia). Then there are three lines, each containing 6 natural numbers: $ a_{100}, a_{50}, a_{20}, a_{10}, a_5, a_1 $ $ b_{100}, b_{50}, b_{20}, b_{10}, b_5, b_1 $ $ c_{100}, c_{50}, c_{20}, c_{10}, c_5, c_1 $ $a_{100}$ is the number of $100$ yuan banknotes Alice has, $b_{50}$ is the number of $50$ yuan banknotes Bob has, and so on. We also guarantee $a_{10} + a_5 + a_1 \le 30$, $b_{10} + b_5 + b_1 \le 30$, $c_{10} + c_5 + c_1 \le 30$, and the total face value of all banknotes owned by the three people does not exceed $1,000$.

If the debts can be fully settled, output the minimum number of banknotes that need to be exchanged. If they cannot be settled, output impossible.

For $30\%$ of the testdata, $x_1, x_2, x_3 \le 50$. For $100\%$ of the testdata, $x_1, x_2, x_3 \le 1,000$. Translated by ChatGPT 5