Problem D
Circle of Debt
The three friends Alice, Bob, and Cynthia always seem to get
in situations where there are debts to be cleared among
themselves. Of course, this is the “price” of hanging out a
lot: it only takes a few resturant visits, movies, and drink
rounds to get an unsettled balance. So when they meet as usual
every Friday afternoon they begin their evening by clearing
last week’s debts. To satisfy their mathematically inclined
minds they prefer clearing their debts using as little money
transaction as possible, i.e. by exchanging as few bank notes
and coins as necessary. To their surprise, this can sometimes
by harder than it sounds. Suppose that Alice owes Bob
Input
On the first line of input is a single positive integer,
Next follow three lines each with six non-negative integers
Output
For each test case there should be one line of output containing the minimum number of bank notes and coins needed to settle the balance. If it is not possible at all, output the string “impossible”.
Sample Input 1 | Sample Output 1 |
---|---|
3 10 0 0 0 1 0 0 0 0 0 0 0 3 0 10 0 0 3 0 0 0 -10 -10 -10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10 10 10 3 0 0 0 2 0 0 2 0 0 0 1 0 0 1 1 0 3 |
5 0 impossible |