TopCoder problem "LogCutter" used in SRM 329 (Division I Level Two)



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 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.

 

Definition

    
Class:LogCutter
Method:bestCut
Parameters:int, int, int, int
Returns:String
Method signature:String bestCut(int L, int A, int K, int C)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
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.
2)
    
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.
3)
    
10000
999983
5000
1000
Returns: "13 2"
4)
    
5
7
100
100
Returns: "1 1"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5955

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10009&pm=5955

Writer:

dmytro

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Greedy, Search, Sorting