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
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
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"
254972011
548485165
5332
7970
Returns: "72465 47271"
261041520
609823152
9321
9397
Returns: "62052 46770"
509814502
367392227
4843
6982
Returns: "218447 214011"
11475485
81287286
6667
5351
Returns: "2474 1867"
889122851
65518436
3044
8813
Returns: "391470 147353"
56771247
279113036
1060
7634
Returns: "110512 36571"
90313815
985328869
7319
8402
Returns: "18113 4699"
723852485
323441038
6055
6048
Returns: "146412 51851"
22797416
180798385
3655
2448
Returns: "16615 7926"
48874477
602748809
105
956
Returns: "12542808 12542808"
2
1
1
1
Returns: "1 1"
1000000000
1000000000
10000
10000
Returns: "999989999 2"
940076323
803471157
9462
8143
Returns: "207654 53254"
940076323 803471157 9462 8143
10000
1
10000
10000
Returns: "1 1"
10001
1
10000
10000
Returns: "1 1"
10002
1
10000
10000
Returns: "2 2"
1000000000
1
10000
10000
Returns: "999989999 2"
10
3
1
5
Returns: "6 4"
1000000
1
10000
10000
Returns: "989999 2"
999999999
283738473
10000
10000
Returns: "412657 410590"
999999997
999999997
9999
9997
Returns: "999989997 2"
722232984
697848970
3256
4879
Returns: "1037546 36558"
1000000000
9997
10000
10000
Returns: "900029999 9998"
999999998
12323133
10000
5122
Returns: "413887 398372"
1000000000
10000
10000
10000
Returns: "899999999 10001"
123456
999999999
9999
50
Returns: "2429 2240"
10000
999983
10000
10000
Returns: "1 1"
14
3
5
4
Returns: "4 3"
999999997
123456789
10000
10000
Returns: "12339462 12339412"
1000000000
999999998
9996
9999
Returns: "999990004 999990004"
100000001
60000001
9996
9999
Returns: "19990012 6"
10
9
10
10
Returns: "9 1"
999999997
537565721
9991
9997
Returns: "256701 211728"
3563
256245245
2
30
Returns: "1473 617"
179424674
999999999
10000
4879
Returns: "369336 364646"
1000000000
1000000000
10000
1
Returns: "999989999 10001"
116517483
416546046
4668
5905
Returns: "39724 811"
1000000000
1000000000
10000
10000
Returns: "999989999 2"
1000000000
100000
10000
9000
Returns: "200000 2"
1000000000
1242357
10000
10000
Returns: "171111 97387"
947957934
999999999
9999
4543
Returns: "253033 109301"