1742: LogCutter

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.

The test contains a case. There will be a line including L,A,K,C. - L will be between 2 and 1000000000, inclusive. - A will be between 1 and 1000000000, inclusive. - K will be between 1 and 1000, inclusive. - C will be between 1 and 1000, inclusive.

Determine a strategy for cutting the log that minimizes the length of the longest resulting piece. The return value should be a String formatted as "MaxPart FirstCut" (quotes for clarity only), where MaxPart is the length of the longest piece and FirstCut is the coordinate of the leftmost cut. Both MaxPart and FirstCut must be integers with no leading zeroes. If there are multiple answers, return the one with the smallest FirstCut value.

9 3 2 1
5 2 1 2
6 3 5 3
5 7 100 100

5 4
3 3
2 1
1 1

0)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. 1)This log of length 5 can only be cut in one place, which is 3 centimeters from the left end of the log. 2) 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.