Allocation Google Kickstart (Round A)(Problem 1) Editorial and Solutions

Allocation Google Kickstart(Round A Problem-1) Editorial and Solution

PROBLEM STATEMENT

YOU CAN FIND THE COMPLETE PROBLEM STATEMENT HERE : PROBLEM STATEMENT

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?

UNDERSTANDING THE PROBLEM:

So the problem is pretty straight forward, we take the input of the users budget and tell him/her the number of houses he/she can afford. So in order to ensure that the maximum houses can be bought we first have to sort the prices in ascending order and put a while loop to check if the price when reduced from budget gives a negative value. If it gives a negative value then we can print the count value or else we can decrease the i-th house price from the budget and increase the count by 1. At the end if the person is able to buy all houses then we print out the number of houses to him. In Kickstart there is a particular output format so don't print in some other way or else even after applying the correct logic you will get WA.

PYTHON 3 CODE:

Now that we know the logic behind the code lets implement it!
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
testcases = int(input())
for i in range(testcases):
	n,b = map(int,input().split())
	houses = list(map(int,input().split()))
	houses =sorted(houses)
	count = 0
	printed = False
	for house in houses:
		if b-house<0:
			print("Case #"+str(i+1)+": "+str(count))
			printed = True
			break
		else:
			b-=house
			count+=1
	if not printed:
		print("Case #"+str(i+1)+": "+str(count))

Comments

Post a Comment