A simple problem pattern in competitive programming

Consider the following two problems appeared in two different competitions, which underlies the same pattern.

Given a number of chocolates (N). For each of M wrappers, we will get a chocolate free. How can one have the maximum number of chocolates by following an optimum strategy?

Given a number of candles (N) each of them burn for 1 hours. Assume that from the remaining wax of M burning candles we can make another candle. What is the maximum number of hours for which we can lit the candles by following the optimum strategy?

The solution is simple. As long as we have more chocolates than M, we continue to eat them and produce N/M wrappers which again fetch some more chocolates. Add it to the remaining chocolates and repeat this procedure until we have less number of chocolates than

Following is the simple C++ program which implements the above algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *