BoardSplitting
SRM 544 · 2011-11-22 · by pieguy
Problem Statement
A construction company recently ordered some boards of length desiredLength from a lumber company. By mistake, the lumber company instead delivered boards of length actualLength. The construction company doesn't have time to reissue the order, so instead they will cut and glue together the boards they have in order to form boards of the proper length.
The construction company needs desiredCount boards of length desiredLength. The have an effectively unlimited supply of boards of length actualLength. The construction company wants to use as few boards as possible. If there are multiple ways to use the same number of boards, they want to perform as few cuts as possible. Return the number of cuts they will perform.
Notes
- A board is a one-dimensional piece of wood. A single board of length L may be cut into two boards of length X and Y, provided X > 0, Y > 0, and X + Y = L. Two boards of length X and Y may be glued together to form a board of length X + Y.
Constraints
- desiredLength will be between 1 and 1000, inclusive.
- desiredCount will be between 1 and 1000, inclusive.
- actualLength will be between 1 and 1000, inclusive.
5 4 4 Returns: 3
We need 4 boards of length 5 each. We have an unlimited supply of boards of length 4. One solution is to cut one board into 4 pieces of length 1 each (using 3 cuts), then glue each piece to a board of length 4.
6 100 3 Returns: 0
No cuts are necessary.
500 5 1000 Returns: 3
We cut 3 boards in half.
314 159 26 Returns: 147
1 1 1 Returns: 0
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BoardSplitting with a public method int minimumCuts(int desiredLength, int desiredCount, int actualLength) · 95 test cases · 2 s / 256 MB per case