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):
Returns
Constraints
2 ≤ n ≤ 105
1 ≤ t ≤ 109
1 ≤ lengths[i] ≤ 109
The sum of the elements of lengths equals the uncut rod length.