PROBLEM STATEMENT
You have a rectangular chocolate bar that consists of width x height square tiles. You can split
it into two rectangular pieces by creating a single vertical or horizontal break along tile edges.
For example, a 2 x 2 chocolate bar can be divided into two 2 x 1 pieces, but it cannot be divided
into two pieces, where one of them is 1 x 1. You can repeat the split operation as many times as
you want, each time splitting a single rectangular piece into two rectangular pieces. Your goal
is to create a piece consisting of exactly nTiles tiles. Return the minimal number of split
operations necessary to reach this goal. If it is impossible, return -1.
DEFINITION
Class:Chocolate
Method:minSplitNumber
Parameters:int, int, int
Returns:int
Method signature:int minSplitNumber(int width, int height, int nTiles)
CONSTRAINTS
-width will be between 1 and 10^9, inclusive.
-height will be between 1 and 10^9, inclusive.
-nTiles will be between 1 and 10^9, inclusive.
EXAMPLES
0)
5
4
12
Returns: 1
You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single
vertical break. Only one break is necessary.
1)
12
10
120
Returns: 0
The chocolate bar consists of exactly 120 tiles.
2)
2
2
1
Returns: 2
3)
17
19
111
Returns: -1
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.