【Kick Start】2020 Round A

这次学习的是Google Kick Start的2020回A轮题目，因为我没有在考试时做这套题目，因此在此作为学习，以弥补自身不足。

点击这里→传送门可以返回到这个系列的List哦

Round A 2020

Problem
There are $N$ houses for sale. The i-th house costs $A_i$ 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 $A_i$ , 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 ≤ $A_i$ ≤ 1000, for all i.

Test set 1
1 ≤ $N$ ≤ 100.

Test set 2
1 ≤ $N$ ≤ 105.

Sample

Input	Output
3
4 100
20 90 40 90	Case #1: 2
4 50
30 30 10 10	Case #2: 3
3 300
999 999 999	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).

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

代码部分

def Calc():
    housesNumber_budget=list(map(int, input().split()))
    houseValue=list(map(int, input().split()))
   
    houseValue.sort()
    valueSum = 0
    for i in range(housesNumber_budget[0]):
        valueSum+=int(houseValue[i])
        if(valueSum>housesNumber_budget[1]):
            i-=1
            break
    return i+1


def main():
    totalNumber=int(input())
    for i in range(totalNumber):
        print("Case #"+str(i+1)+": "+str(Calc()))

if __name__=="__main__":
    main()

Problem
Dr. Patel has $N$ stacks of plates. Each stack contains $K$ plates. Each plate has a positive beauty value, describing how beautiful it looks.

Dr. Patel would like to take exactly $P$ plates to use for dinner tonight. If he would like to take a plate in a stack, he must also take all of the plates above it in that stack as well.

Help Dr. Patel pick the $P$ plates that would maximize the total sum of beauty values.

Input
The first line of the input gives the number of test cases, $T$ . $T$ test cases follow. Each test case begins with a line containing the three integers $N$ , $K$ and $P$ . Then, $N$ lines follow. The i-th line contains $K$ integers, describing the beauty values of each stack of plates from top to bottom.

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 total sum of beauty values that Dr. Patel could pick.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ $T$ ≤ 100.
1 ≤ $K$ ≤ 30.
1 ≤ $P$ ≤ $N * K$ .
The beauty values are between 1 and 100, inclusive.

Test set 1
1 ≤ $N$ ≤ 3.

Test set 2
1 ≤ $N$ ≤ 50.

Sample

Input	Output
2
2 4 5
10 10 100 30
80 50 10 50	Case #1: 250
3 2 3	Case #2: 180
80 80
15 50
20 10

In Sample Case #1, Dr. Patel needs to pick $P$ = 5 plates:
He can pick the top 3 plates from the first stack (10 + 10 + 100 = 120).
He can pick the top 2 plates from the second stack (80 + 50 = 130) .
In total, the sum of beauty values is 250.

In Sample Case #2, Dr. Patel needs to pick $P$ = 3 plates:
He can pick the top 2 plates from the first stack (80 + 80 = 160).
He can pick no plates from the second stack.
He can pick the top plate from the third stack (20).
In total, the sum of beauty values is 180.

Note: Unlike previous editions, in Kick Start 2020, all test sets are visible verdict test sets, meaning you receive instant feedback upon submission.

代码部分

第三部分内容

第四部分内容