1.
Milestone - Coding - Python - 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 cutThemAl/ in the editor
below.
cutThemAl/ 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"
Function
Sample Input For Custom Testing
STDIN
4
3
4
3
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.
lengths[] size n = 4
lengths[] = [3, 5, 4, 3]
minLength= 9
Sample Input For Custom Testing
Function
lengths[] size n = 3
lengths[] = [5, 6, 2]
STDIN
2
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.
minLength= 12
***********************************************************
l=len(lengths)
top=[]
top.append(lengths[0]+lengths[1])
for i in range(2,l):
top.append(lengths[i])
print(top)
bot=[]
bot.append(lengths[l-1]+lengths[l-2])
for j in range(l-2,0,-1):
bot.append(lengths[j])
print(bot)
for i in range(0,len(top)-1):
while i<len(top)-1:
cost=sum(top)-top[i]
if sum(top[(i+1):])<minLength:
res1='Impossible'
break
break
for i in range(0,len(bot)-1):
while i<len(bot)-1:
cost=sum(bot)-bot[i]
if sum(bot[(i+1):])<minLength:
res2='Impossible'
break
break
if res1!='Impossible' or res2!='Impossible':
return 'Possible'
else:
return 'Impossible'
******************************************************************
