Ramu and Jithin want to watch the grand finale, but unfortunately, they could not get tickets to the match. However, Ramu is not someone who gives up so easily and he has a plan to watch the match. The field where the match is played is surrounded by a wall with height K. Outside, there are N boxes (numbered 1 through N). For each valid i, the ith box has a height Hi.
Ramu wants to take some boxes and stack them on top of each other to build two towers. The height of each tower is the sum of heights of all the boxes that form it. Of course, no box may be in both towers. The height of each tower should be at least K. Then Ramu can climb on top of one tower and Jithin on top of the other, and they can watch the match uninterrupted!
While Ramu is busy stacking the boxes, Jithin would like to know the smallest number of boxes required to build two towers such that each of them has height at least K, or at least that it is
impossible to build such towers. Can you help Jithin ?
Inputs:
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K.
The second line contains N space-separated integers H1,H2,..,HN.
Ex:
2
8 38
7 8 19 7 8 7 10 20
4 5
2 10 4 9
Output:
For each test case, print a single line containing one integer – the smallest number of boxes required to build two towers, or −1 if it is impossible.
Ex:
7
2
Python Solution
print("Enter the total test case\n")
total_test = int(input())
for test_case in range(total_test):
print("Enter the number of box and total height of stadium seperated by Space\n")
n_box,height = list(map(int, input().split()))
print("Enter {} box height seperated by Space".format(n_box))
height_lst = list(map(int, input().split()))
height_lst.sort(reverse=True)
sum = height_lst[0]
sum_lst_1 = set()
res = -1
sum_lst_1.add(height_lst[0])
for i in range(1, len(height_lst)):
s2 = set()
sum+=height_lst[i]
for ele in sum_lst_1:
s2.add(height_lst[i])
if (ele >= height and sum - ele) >=height or \
(ele + height_lst[i] >= height and \
sum - ele -height_lst[i]>=height):
res = i
break
s2.add(ele + height_lst[i])
s2.add(ele)
if res != -1:
break
sum_lst_1 = s2
if res == -1:
print(res)
else:
result =res+1
print ("The smallest number of boxes required : ",result)Output
Enter the total test case
1
Enter the number of box and total height of stadium seperated by Space
8 38
Enter 8 box height seperated by Space
7 8 19 7 8 7 10 20
The smallest number of boxes required : 7
Please bookmark this page and refer to friends.
Reference
