A spellcaster is given an object (e.g. mouse, owl, dwarf, purse ...) and a set of spells that she / he can use to transform the object. The
effect of each spell is described by a set of from-to pairs. For example, spell "Chiroptera" may transform objects as follows:
crocodile -> dragon
mouse -> bat
If the spell is cast on an unspecified inital form, the form of the object is not changed.
The spellcaster possesses some finite amount of magical energy (an integer > 0). Each spell casting, whether fruitful or not, consumes
certain amount of magical energy (an integer > 0). Write a program that helps the spellcaster to transform the object into desired form in the most energy-efficient way.
The program inputs the description of spells, the amount of available magical energy, the initial object form, and the desired object form.
If desired transfiguration is possible, the program should print the appropriate sequence of spells to achieve the desired form. The sequence
of spells should consume the least possible amount of magical energy.
If the transformation is not possible the program should print:
TRANSFORMATION IS IMPOSSIBLE
Input data format:
------------------
The input data will be given in the following format:
number of spells (K)
name of spell 1 \
amount of energy consumed by spell 1 \
number of transformation pairs (N1) \
initial form 1 \
resultant form 1 \
initial form 2 information about spell 1
resultant form 2 /
... /
initial form N1 /
resultant form N1 /
name of spell 2 \
amount of energy consumed by spell 2 \
number of transformation pairs (N2) \
initial form 1 \
resultant form 1 \
initial form 2 information about spell 2
rtesultant form 2 /
... /
initial form N2 /
target form N2 /
...
...
...
name of spell k \
amount of energy consumed by spell k \
number of transformation pairs (Nk) \
initial form 1 \
resultant form 1 \
initial form 2 information about spell 2
rtesultant form 2 /
... /
initial form Nk /
target form Nk /
available amount of magical energy
initial form of the object
desired form of the object
You can assume that both the number of spells (K) and the number of
transformation pairs within a spell (N) are all less than 100, and that
amounts of magical energy are positive numbers < 1000000.
Example:
--------
Given below is an example input to the transfiguration program.
The input defines:
* two spells:
CHIROPTERA (each casting consumes 4 units of magical energy):
crocodile -> dragon
mouse -> bat
and REDUCTIO (each casting consumes 1 unit of magical energy):
elephant -> hyppo
hyppo -> horse
horse -> mouse
mouse -> elephant
* 8 units of available magical energy
* initial object "elephant"
* desired object form is "bat"
---- Input: ----
2
CHIROPTERA
4
2
crocodile
dragon
mouse
bat
REDUCTIO
1
4
elephant
hyppo
hyppo
horse
horse
mouse
mouse
elephant
8
elephant
bat
--------------------
In response to this input, your program should output:
REDUCTIO
REDUCTIO
REDUCTIO
CHIROPTERA
That output defines sequences of four transformations:
(Initial object: elephant; initial magical energy: 8 units)