Bowling Score Assistant

Bowling is a very popular sport in the United States. Working out how many pins you still need in order to win a game is tedious, so you are writing a program that does the work.

If you have never bowled or do not remember how scoring works, the hint section spells out the rules. Only one thing decides the game. Your final score has to be higher than your opponent's.

You are given your opponent's final score and the number of pins you knocked down on every ball through the eighth frame. Decide whether the rolls left in frames 9 and 10 can still win. If they can, print the winning sequence of rolls that comes first in lexicographical order, that is, the one with the lowest first roll, then the lowest second roll given that first roll, then the lowest third roll given the first two, and so on. If nothing wins, print impossible.

The input is a series of test cases. Each case starts with your opponent's final score, followed by the number of pins knocked down on each of your rolls for the first eight frames. A negative number ends the input.

Your opponent's score is an integer from 0 to 300. Each roll knocks down an integer number of pins from 0 to 10, where 10 is the number of pins standing at the start of a frame. Apart from the negative number that ends the input, every value is a pin count that a real game can produce.

The sample input is laid out neatly only so the case boundaries are easy to see. The real input makes no promise about spacing or line breaks, so you have to apply the frame rules yourself to find where one case ends and the next one begins.

For each case, print the rolls you need in order to win, one case per line. Follow this format exactly: Case, one space, the case number, a colon, one space, and the answer for that case. The answer is either impossible or the required pin counts in order, with exactly one space between each pair of numbers and no trailing space.

Ten pins are set up, and you knock them down by rolling a ball at them.

For each set of ten pins, if you do not knock them all down with your first ball, you get a second try.

The one or two balls you roll at a set of ten pins are called a frame, and a game has ten frames.

Knocking all ten pins down with the first roll is a strike. Knocking all ten down but needing both rolls is a spare.

The score is the sum of the pins you knock down, with the bonuses for spares and strikes described below. If you never get a spare or a strike, your score is simply the total of your twenty rolls.

After a strike you count the next two rolls a second time. After a spare you count the next one roll a second time.

The tenth frame is special, because the next roll after a strike or a spare there would not normally exist. On a spare in the tenth frame you get one more roll at a fresh set of ten pins, and that roll is added to the 10 you scored for the spare. On a strike in the tenth frame you get two more rolls, and if the first of them is also a strike, the second one is rolled at another fresh set of ten pins. The rolls do not go on forever when the strikes keep coming. You get only two rolls after the first strike of the tenth frame, and they are added to the 10 for that strike, so the tenth frame is worth at most 30. Every other frame is worth at most 30 as well.

So the tenth frame can hold three rolls, and a game has at most $2 \times 9 + 3 = 21$ rolls. The fewest rolls happen when you strike in each of the first nine frames and then get neither a strike nor a spare in the tenth, which takes $9 + 2 = 11$ rolls.

Each table below lists the pins knocked down over ten frames. The first row is the frame number and the second row is the pins knocked down in that frame.

Game 1

There is no spare and no strike, so the score is just the sum of these numbers, which is 79.

Game 2

This is game 1 with a spare in frame 1 and a strike in frame 5. Frame 1 is worth 10, and then the 6 that opens frame 2 is counted a second time. Because of the strike in frame 5, the two rolls of frame 6 are counted a second time as well. The final score is 97.

Game 3

This is game 2 with a strike in frame 6. Two more pins go down, so the score before bonuses is 85 instead of the 83 of game 2. As before, the first roll of frame 2 is counted twice, which gives 91. Next, the two rolls after the strike in frame 5, a 10 and a 7, are counted again, which gives 108. Finally the two rolls of frame 7 are counted again, which gives 117.

Game 4

This is game 3 with a spare in frame 10. The extra pin on the second roll of the tenth frame brings the score to 118 by the same computation as in game 3, and the 7 on the last roll is added to the spare, so the total is 125.

Game 5 is a perfect game.

Every frame is a strike, so the score is the maximum of 300.