Saved Bookmarks
| 1. |
After somehow escaping from the previous castle, pangs of hunger grip him. Mario visits a chocolate store nearby where the shopkeeper has 9 jars filled with 4,2,6,7,3,4,5,8,3 jellyfishes respectively. Each second he is allowed to either double the content of one jar, or eat 9 jellyfishes (one from each jar). Can Mario always empty all the jars using these moves?If yes, then give the minimum time required to empty the jars ? (Answer 0 if no) |
|
Answer» Solution : First note that a jar shall not become zero with other jars being nonzero.(Think !). Yes mario can always empty the jars. Basic idea is to reduce one from every jar until a jar contains only one, then double that jar and CONTINUE. This will ensure emptying, though notin minimum steps. For minimum steps we shall reduce the unnecessary steps. The method is to first double each jar until it reaches a number less than or equal to the highest number, then deduct all jars by one until a jar BECOMES one OR if a jar can again be doubled under above condition (note that this doubling will not add any extra work & infact reduce some.). Then check above rule after every deduction & double the necessaryjars. For eg, CONSIDER only 2 jars with 1 4 as initial counts. Then he shall follow these steps 1. Double the jar 1 (GIVES 2 4 ) 2. Double the jar 1 (gives 4 4 ) 3. Reduce both jars one by one `(3 3 gt 2 2 gt 1 1 gt 0 0 )` ( 4 times )Which gives 6as the minimum steps to empty the jars.eg 2: in the case 2 6 8, the number shall drop as follows (11 steps)2 6 8 gtgt 4 6 8 gtgt 8 6 8 (double each jar close to highest number)`8 6 8 gt 7 5 7 gt6 4 6 gt 5 3 5 gt4 2 4` (reduce all ONLY until there is a double possibleagain!)`4 2 4 gtgt 4 4 4 gt3 3 3gtgt2 2 2gtgt1 1 1gtgt0 0 0`(then follow same procedure)Now that you have an idea, the original question will be easy to answer.   Which gives that minimum 19 steps are required for emptying the jars. |
|