Class name: FeedTheCat
Method name: measure
Parameters: int, int, int
Returns: int
A man needs to feed his cat an exact amount of cat food. However, he only has
two measuring bins. The man wants to spend as little time measuring as
possible.
Find the minimum number of actions the man needs to take in order to measure
the exact amount of cat food into one of the two containers. If it is not
possible to come up with the exact amount necessary, return -1.
Possible actions (each counts as +1)
1) Fill a container to the top
2) Empty a container back into the cat food bin
3) Fill one container from the other container (removes enough from A to fill B
totally or to empty A completely or vice versa)
The final status should be with one of the containers filled with targetFood
amount of cat food.
Implement a class FeedTheCat which contains a method measure. The method takes
3 ints as parameters: a target and the size of the two containers and returns
an int that is the minimum number of actions required to reach the target.
int measure(int targetFood, int containerA, int containerB)
INPUT:
targetFood: an integer between 1 and 100, inclusive
containerA: the max amount the first container can hold, between 1 and 100
inclusive
containerB: the max amount the second container can hold, between 1 and 100
inclusive
TopCoder will check the validity of the input.
OUTPUT:
The minimum number of actions it takes to fill one of the containers with
exactly targetFood amount of cat food (using the list of actions above). If it
is not possible, return -1.
EXAMPLES:
targetFood = 4
containerA = 5
containerB = 6
The shortest way to reach 4 is: fill 5 with food, empty 5 into 6, fill 5 with
food, empty 5 into 6. 5 now has 4 units of cat food.
returns: 4
targetFood = 12
containerA = 13
containerB = 2
To reach 12, we fill B, and empty B into A 6 times, for a total of 12 actions.
returns: 12
targetFood = 12
containerA = 5
containerB = 19
returns: 22
targetFood = 5
containerA = 10
containerB = 2
returns: -1
|