The tell-tale heart P46494


Statement
 

pdf   zip

html

The old man was dead…First of all I dismembered the corpse. I cut off the head and the arms and the legs…There was nothing to wash out –no stain of any kind –no blood-spot whatever. I had been too wary for that. A tub had caught all –ha! ha!

So our hero has a big tub full with the blood of the old man he has just killed. He also has several empty smaller tubs, where (in his madness) he has decided to distribute the blood to hide it from the policemen that will arrive soon to investigate. Every tub has an exact integer capacity. Obsessed with details, our hero wants to distribute the blood evenly among all the tubs, included the bigger tub that now contains all the blood. To achieve this, and as many times as he likes, all he can do is to choose any non-empty tub x and any other non-full tub y, and pour blood from x into y until x becomes empty, or until y becomes full (or both).

Our hero can already hear the hearts of some policemen approaching his home’s door, so he will have to rush! Please help this nice gentleman, telling him the minimum number of movements needed to reach a situation where all the tubes have exactly the same quantity of blood.

Input

Input consists of several cases, one per line. Each line has between 1 and 10 integer numbers for the capacities of the tubs, all between 1 and 20. The first number of every case is the capacity of the larger tub, initially full with blood. All the numbers of the same case are different. Every given case is either unsolvable or solvable in at most 10 movements.

Output

For every case, print its number, followed by the minimum number of movements needed to evenly distribute the blood. If it is impossible, state so.

Hint

A plain brute-force solution should be much too slow for this problem.

Public test cases
  • Input

    10
    2 1
    6 5 2
    16 15 4 12
    7 5 6
    12 7 3
    12 11 9 5 3 2
    16 2 5 6 7 8 9 10
    

    Output

    Case #1: 0
    Case #2: 1
    Case #3: 3
    Case #4: 4
    Case #5: impossible
    Case #6: impossible
    Case #7: 8
    Case #8: 10
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Final
    Date
    2008-10-01