Maddox Smith Staff asked 5 years ago

Use to Transform The Object

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)   1. REDUCTIO    (transforms elephant into hyppo, consumes 1 unit, remaining energy: 7)   2. REDUCTIO    (transforms hyppo into horse, consumes 1 unit, remaining energy: 6)   3. REDUCTIO    (transforms horse into mouse, consumes 1 unit, remaining energy: 5)   4. CHIROPTERA  (transforms mouse into bat, consumes 4 unit, remaining energy: 3)