Cut Them All
An automated cutting machine is used to cut rods into segments. The cutting machine can only hold a rod of minLength or more. A rod is marked with the necessary cuts and their lengths are given as an array in the order they are marked. Determine if it is possible to plan the cuts so the last cut is from a rod at least minLength units long.
Example
n = 3
lengths = [4, 3, 2]
minLength = 7
The rod is initially sum(lengths) = 4 + 3 + 2 = 9 units long. First cut off the segment of length 4 + 3 = 7 leaving a rod 9 - 7 = 2. Then check that the length 7 rod can be cut into segments of lengths 4 and 3. Since 7 is greater than or equal to minLength = 7, the final cut can be made. Return “Possible”.
Example
n = 3
lengths = [4, 2, 3]
minLength = 7
The rod is initially sum(lengths) = 4 + 2 + 3 = 9 units long. In this case, the initial cut can be of length 4 or 4 + 2 = 6. Regardless of the length of the first cut, the remaining piece will be shorter than minLength. Because n - 1 = 2 cuts cannot be made, the answer is “Impossible.”
Function Description
Complete the function cutThemAll in the editor below.
cutThemAll has the following parameter(s):
int lengths[n]: the lengths of the segments, in order
int minLength: the minimum length the machine can accept Returns
string: “Possible” if all n-1 cuts can be made. Otherwise, return the string “Impossible” Constraints
2 ≤ n ≤ 105 1 ≤ t ≤ 109 1 ≤ lengths[i] ≤ 109 The sum of the elements of lengths equals the uncut rod length.
Input Format For Custom Testing The first line contains an integer, n, the number of elements in lengths.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer, lengths[i].
The next line contains an integer, minLength, the minimum length accepted by the machine.
Sample Case 0 Sample Input For Custom Testing
STDIN Function
4 → lengths[] size n = 4 3 → lengths[] = [3, 5, 4, 3] 5 4 3 9 → minLength= 9 Sample Output
Possible Explanation
The uncut rod is 3 + 5 + 4 + 3 = 15 units long. Cut the rod into lengths of 3 + 5 + 4 = 12 and 3. Then cut the 12 unit piece into lengths 3 and 5 + 4 = 9. The remaining segment is 5 + 4 = 9 units and that is long enough to make the final cut.
Sample Case 1 Sample Input For Custom Testing
STDIN Function
3 → lengths[] size n = 3 5 → lengths[] = [5, 6, 2] 6 2 12 → minLength= 12 Sample Output
Impossible Explanation
The uncut rod is 5 + 6 + 2 = 13 units long. After making either cut, the rod will be too short to make the second cut.
Solution
To solve this problem, you can follow these steps:
Initial Check: First, sum all elements in the
lengths
array. If the sum is less thanminLength
, return “Impossible”.Iterative Check: Start from the beginning of the
lengths
array and keep a running sum.- At each step, check if the remaining length of the rod (
totalLength - runningSum
) is greater than or equal tominLength
. - If yes, then we should also check if the
runningSum
itself can be broken down into the lengths in the array leading up to this point.
- At each step, check if the remaining length of the rod (
Final Check: If you find such a configuration, return “Possible”. If you exhaust all possibilities, return “Impossible”.
Here’s a Python function to implement this algorithm:
|
|
In this function, runningSum
keeps track of the length of the rod at the current step, and tempSum
checks if the remaining lengths in the array can sum up to the minLength
.
This should solve the problem as specified.