Allocation in python - Kickstart solution

Solution for Kickstart problem Allocation in python

Problem

There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend.

What is the maximum number of houses you can buy?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the two integers N and B. The second line contains N integers. The i-th integer is Ai, the cost of the i-th house.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

Limits

Time limit: 15 seconds per test set.

Memory limit: 1GB.

1 ≤ T ≤ 100.

1 ≤ B ≤ 105.

1 ≤ Ai ≤ 1000, for all i.

Test set 1

1 ≤ N ≤ 100.

Test set 2

1 ≤ N ≤ 105.

Sample

Input 

3

4 100

20 90 40 90

4 50

30 30 10 10

3 300

999 999 999

Output 

Case #1: 2

Case #2: 3

Case #3: 0

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars.

In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars.

In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).

Procedure :

1. Start.

2. Get the number of test cases from user.

3. check if test case is not greater than 100 and not less than 1.

4. loop(0 to test case)

5. Get the number of houses and budget from user.

6. check if the constraint for house budget is met.

7. Get the price of n houses and store it in a list.

8. Sort the list.

9. Iterate through the list.

10. If price is less than total budget 

        => increment a count variable

        => subtract the price of the house in total budget.

11. Print the count.

12. End

Code :

#Get the number of testcase from user

t_case = int(input())

#checking the constraint for number of test cases

if(100>=t_case>=1):

    for k in range(t_case):

        #Get the number of houses and budget from user

        house_budget=list(map(int,input().split()))

        #check if the constraint for house budget is met

        if((1 <= house_budget[0] <= 10**5)and(1 <= house_budget[1] <= 10**5)):

            #get price of n houses

            A=list(map(int,input().split()))

            A.sort()

            count=0

            for i in range(len(A)):

                #if price is less than budget increase the count

                if(house_budget[1]>=A[i]):

                    count+=1

                    #subtract the price from total budget

                    house_budget[1]=house_budget[1]-A[i]

            #print the count for each test case

            print("Case #"+str(k+1)+":",count)