Question:
A man is planning to move to another place. He consults many Movers and Packers companies for a price to move his entire belongings to his designated place. Firstly, all the companies ask the man for the number of cartons he requires to pack his items. Each cartons can carry a maximim weight of K units. The man lists out the weight of N number of items(a[]) he wants to pack. The task here is to find minimum number of cartons the man has to order to pack all his items.
Note:
1. Each carton can carry at most 2 items, and the sum of the weights of these items should not be more than the maximum weight that the carton can carry.
2. All the cartons are of same types.
3. The weight of any item should not be more than K, a[i]<=K for i.
Example 1:
Input:
5->Value of N
5->Value of K
{5,2,3,1,4}-> a[]. Elements a[0] to a[n-1], where each input elements is separeted by a newline.
Output:
3
Explanation:
From the input given above:
Number of items: 5
Maximum weight the carton can carry: 5 units
Carton Number Item weight
Carton 1 5
Carton 2 2 3
Carton 3 1 4
From the above table, 3 cartons are required to carry the items. Hence the output is 3.
Example 2:
Input:
7->Value of N
12->Value of K
{12,2,3,11,6,8,1}-> a[]. Elements a[0] to a[n-1], where each input elements is separeted by a newline.
Output:
6
Explanation:
From the input given above:
Number of items: 7
Maximum weight the carton can carry: 12 units
Carton Number Item weight
Carton 1 12
Carton 2 11 1
Carton 3 3 8
Carton 4 2 6
From the above table, 6 cartons are required to carry the items. Hence the output is 6.
Solution: In Python3
def cs(a, m, k):
c = 0
for i in range(0, m):
s = 0;
for j in range(i, m):
if (s + a[j] < k):
s = a[j] + s
c+= 1
else:
break
return c
m=int(input())
k=int(input())
a=list(map(int,input().split()))
c = cs(a, m, k)
print(c-2)
#print(m,k,a)Also Checkout