CODEWITHSUNDEEP
pythonpython-3.x
Hanson Sin
Hanson Sin

Reputation: 37

Google Kick Start 2020 Round A wrong answer

link to the problem: https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56

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.

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

Sample 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).

Here is my solution in Python 3:

for i in range(int(input())):
    n, b = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    num = 0
    count = 0
    while num < b:
        num += a[count]
        count += 1
    thei = i + 1
    if num == b:
        print("Case #" + str(thei) + ": " + str(count))
    else:
        cout = count - 1
        print("Case #" + str(thei) + ": " + str(cout))

I can't see any mistake in it, but it keep showing me "RE" (Runtime Error)

the error

Upvotes: 1

Views: 257

Answers (1)

trincot
trincot

Reputation: 350310

The problem occurs when all houses can be bought and you still have budget left. In that case the while loop will continue and a[count] will be an invalid access in a.

Without modifying more than needed, you would add an extra condition in the while loop: and count < len(a). You also need to change the if condition after the loop to if num <= b.

Another solution

The above will fix your issue. Still, the variable names are not so clear; there is repetition of code for the output; we could do without the num variable if we would reduce the budget in the iterations; and why not a for loop instead of a while loop:

for case in range(int(input())):
    _, budget = map(int, input().split())
    prices = list(map(int, input().split()))
    prices.sort()
    for house, price in enumerate(prices):
        if budget < price:  # cannot buy this house
            break
        budget -= price
    else:  # all houses can be bought
        house = len(prices)
    print("Case #{}: {}".format(case + 1, house))

Upvotes: 1

Related Questions