The Mugs Game ------------- In the mugs game, the player is provided with a set of N (2 <= N <= 10) empty mugs in a row, numbered 1 to N. Each mug has a capacity, specified in ounces. The mugs are in a fixed order. The player then executes a series of moves, from the following list: 1. Fill up mug 1 to its capacity. 2. Pour the contents from some mug x into mug x+1 until either mug x is empty or mug x+1 is full. This operation can only be done from one mug into the mug after it, numerically. 3. Pour the contents of mug N down the drain, so that mug N is empty. Note that this can only be done with the last mug N, not with an arbitrary mug. For example, if there were two mugs of capacities 3 and 2 (in order) the player could execute the following sequence of moves: 1. Fill mug one to the top 2. Pour 2 ounces from mug 1 into mug 2 3. Pour out the contents of mug 2 4. Pour 1 ounce from mug 1 to mug 2 The player's goal is to have a specified number of ounces in each mug. For example, if the goal were to have 0 ounces in mug 1 and 1 ounce in mug 2, then the goal would have been reached after move 4 above. In order to win the game, the player must have EXACTLY the amount specified in all mugs simultaneously. Input ----- A sequence of cases, each consisting of a sequence of integers. The first integer is N, the number of mugs. The next N integers are the capacities of the mugs in order. The following N integers are the goals for each mug, in order. This is, for each mug, the EXACT number of ounces to be left in the mug at the end of the game. There are 2N+1 integers per test case with N mugs. Integers are separated by any kind of whitespace, pos- sibly including tabs and newlines. Input ends with an end of file. Output ------ For each test case, output a single line containing just the minimum number of moves necessary to reach the goal. However, if it is not possible to reach the goal, output instead a single line containing nothing but the word `impossible'. Example Input ------- ----- 2 3 2 0 1 3 4 3 2 0 0 1 3 4 3 2 3 2 2 3 4 3 2 1 2 1 Example Output ------- ------ 4 8 13 impossible File: mugs.txt Author: Tom Widland , edited by Bob Walton Date: Sun Oct 9 07:03:12 EDT 2005 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): \$Author: walton \$ \$Date: 2005/10/09 11:03:58 \$ \$RCSfile: mugs.txt,v \$ \$Revision: 1.3 \$