Inside a room, there is a monster with N heads, and a human (with 1 head). The human has two laser guns. The first gun, A destroys C1 heads when fired and the second gun,B destroys C2 heads when fired [The guns may destroy both the monster's as well as human heads, but the guns prioritize monster heads over human ones].
Also, if after the firing of the gun the monster has a positive non-zero number of heads left, the monster will grow additional heads. The monster grows G1 heads when gun A is used and it grows G2 heads when gun B is used.
The problem is to input N, C1, C2, G1 and G2, then find out what would be the shortest combination of gun-choice(A or B) the human must use to kill the monster(the monster dies when No. of heads=0).
I asked for help on the Codecall Forums to solve it, and a member, zoranh has solved the problem for me in C++. The solution makes use of Dijkstra's algorithm and it works with any number of guns. You can download the solution here.
And of course, if you have found an alternative method do post it here!!
Interested in solving more C++ puzzles? Get your copy of Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions
