Problem S. 48. (November 2009)
S. 48. You are given some tanks with known volume, initially all full of water, further, an unlimited water supply. In every step you can do one of the
- pour out the full content of a tank;
- completely refill a tank by using the unlimited water supply;
- pour some water out of a tank into another one, thus filling it up completely;
- pour some water out of a tank into another one, so that the first tank becomes empty (but the second one can not overflow).
Your program should determine whether it is possible -- and if possible, how -- to measure out exactly a prescribed amount of water by repeatedly applying the above rules. Data are read from the standard input, and the result is written to the standard output.
There are two integers (separated by a space) in the first line of the input: the number of tanks 2N4 and the amount of water 1V30 to be measured out. Then each of the following N lines contains an integer: capacity of the ith tank, 1Ci30, is found in the (i+1)th line.
If the prescribed amount of water can be measured out, then the output should be the minimal number of steps L; otherwise the output is ``-1''. If the amount of water can be measured out, the next L lines of the output should contain two integers (separated by a space): the first number is the number of the source tank, while the second number is that of the destination. If the first or second rule (of the four rules above) is applied, instead of a number, a ``*'' character should appear in the appropriate position. (Therefore, the ``*'' character represents a tank with infinite capacity.) If there is more than one solution, any of them can be given by your program.
In the table, ``Példa bemenet'' is the sample input, while ``kimenet'' is output.
The source code and project files of your solution-without the s48.exe or any other auxiliary files generated by the compiler-should be submitted together with a short documentation in a compressed folder s48.zip.
You may download the sample inputs and corresponding outputs from here.
Deadline expired on 10 December 2009.