DWITE Online Computer Programming Contest

Sugar Rush

November 2012
Problem 1

After collecting all the candy you could get at Halloween, you decided to eat all of that candy as fast as possible! However, after having eaten some of them you get a sugar rush, enabling you to eat the remaining pieces even faster! Before starting, you want to calculate how long it will take you to eat all of your candy. From previous Halloweens, you noticed that you start eating one piece of candy at a time (i.e. one piece per mouthful). However, after having eaten C pieces, the sugar rush kicks in and you can eat twice as many pieces of candy at a time. Then after having eaten another C pieces, the amount you can eat at a time is doubled yet again! This continues until you finish all of your candy!

Note: You can only get one sugar rush at a time, even if you eat 2×C pieces of candy in one mouthful.

The input file DATA1.txt will contain 5 test cases. Each test case is a line with two integers, 1 ≤ N, C ≤ 100, representing the (N)umber of pieces of candy you have and the (C)ount of pieces necessary for a sugar rush.

The output file OUT1.txt will contain 5 lines of output. Each is a single integer – the minimum number of mouthfuls necessary to eat all N pieces of candy, in the respective test case.

Sample Input (first 2 shown):
10 1
10 5
Sample Output (first 2 shown):

Explanation of sample: In the first case, the number of pieces doubles after each one. The entire batch is finished as 1 + 2 + 4 + 3 = 10, just 4 steps. The last step could have been up to 8 pieces large, but only 3 pieces of candy remained at that point. The second case has only a single sugar rush that matters, the one after 5 pieces. So the solution is 1 + 1 + 1 + 1 + 1 + 2 + 2 + 1 = 10, which is 8 steps.