Chocolate
SRM 321 · 2006-10-02 · by Mike Mirzayanov
SRM 321 · 2006-10-02 · by Mike Mirzayanov · Simple Search, Iteration
Problem Statement
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.
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
4)
10 5 86 Returns: -1
Submissions are judged against all 247 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Chocolate with a public method int minSplitNumber(int width, int height, int nTiles) · 247 test cases · 2 s / 256 MB per case