LogCutter
SRM 329 · 2006-12-09 · by dmytro
Problem Statement
A lumberjack needs to transport a log to a paper mill. However, it's too long to fit in his truck, so he needs to cut it into multiple pieces. The log's length is L centimeters, and due to its nonuniform density, it can only be cut at certain places. The points at which it can be cut are represented by the expression ((A * i) mod (L - 1)) + 1, for all integers i between 1 and K, inclusive. Coordinates are measured as the distance in centimeters from the leftmost end of the log. The lumberjack is allowed to make at most C cuts.
Determine a strategy for cutting the log that minimizes the length of the longest resulting piece. The return value should be a
Constraints
- L will be between 2 and 1000000000, inclusive.
- A will be between 1 and 1000000000, inclusive.
- K will be between 1 and 10000, inclusive.
- C will be between 1 and 10000, inclusive.
9 3 2 1 Returns: "5 4"
This log of length 9 can be cut at points 4 and 7. We cut it at point 4 to produce two parts with lengths 4 and 5.
5 2 1 2 Returns: "3 3"
This log of length 5 can only be cut in one place, which is 3 centimeters from the left end of the log.
6 3 5 3 Returns: "2 1"
This log of length 6 can be cut at any integer coordinate. We are allowed up to 3 cuts, so we can make the longest part 2 centimeters long. This requires only two cuts at points 2 and 4. To minimize the coordinate of the leftmost cut, we perform a third cut at point 1.
10000 999983 5000 1000 Returns: "13 2"
5 7 100 100 Returns: "1 1"
940076323 803471157 9462 8143 Returns: "207654 53254"
940076323 803471157 9462 8143
Submissions are judged against all 46 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LogCutter with a public method string bestCut(int L, int A, int K, int C) · 46 test cases · 2 s / 256 MB per case