PROBLEM STATEMENT
You have N bottles, each with unlimited capacity. Initially, each bottle contains exactly 1 liter
of water. You want to carry these bottles to another location, but you can only carry K bottles
at a time. You don't want to waste any water and you don't want to make more than one trip, so
you decide to redistribute the contents of the bottles until you end up with no more than K
non-empty bottles.
You are only allowed to redistribute your water using the following method. First, pick two
bottles that contain an equal amount of water. Then, pour the entire content of one of those
bottles into the other. Repeat this process as many times as necessary.
Because of this restriction, it may be impossible to end up with no more than K non-empty bottles
using only the N bottles that you have initially. Fortunately, you can also buy more bottles.
Each bottle that you buy will contain exactly 1 liter of water and have unlimited capacity. For
example, consider the case where N is 3 and K is 1. It's impossible to get from 3 bottles to 1.
If you pour one bottle into another, you end up with one 2 liter bottle and one 1 liter bottle.
At that point, you're stuck. However, if you then buy another bottle, you can pour that bottle
into the 1 liter bottle, and pour the resulting 2 liter bottle into the other 2 liter bottle to
end up with just one 4 liter bottle.
Return the minimum number of additional bottles you must buy in order to achieve your goal. If
it's impossible, return -1 instead.
DEFINITION
Class:PouringWater
Method:getMinBottles
Parameters:int, int
Returns:int
Method signature:int getMinBottles(int N, int K)
CONSTRAINTS
-N will be between 1 and 10^7, inclusive.
-K will be between 1 and 1000, inclusive.
EXAMPLES
0)
3
1
Returns: 1
The example from the problem statement.
1)
13
2
Returns: 3
If you have 13, 14, or 15 bottles, you can't end up with one or two bottles. With 16 bottles, you
can end up with one bottle.
2)
1000000
5
Returns: 15808
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.