Google OA-2 2023

Problem Description

You are given N toys in a shop, each with a price represented in an array A. You have a budget of C to spend on toys, and there are K broken toys that you want to avoid purchasing.

For each of the Q queries, your task is to determine the maximum number of toys you can buy without exceeding your budget and while excluding the broken toys.

Notes

• Use 1-based indexing.
• Query definition:
  • The first element represents an integer C, where C =Query[i][0].
  • The second element represents an integer K, where K = Query[i][1].
• The next K integers represent the indices of broken toys which are Query[i][j] for all j> 1.
• Treat each query independently.

Function description

Complete the solve function. This function takes the following 4 parameters and returns an array of an answer to the query

• N. Represents the size of array A
• A: Represents the array of costs of each toy
• Q: Represents the number of queries
• Query: Represents the query array

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

The first line contains T, which represents the number of test cases.

For each test case:

• The first line contains a single integer N representing the size of the array 
• The second line contains N space-separated integers representing the cost of toys.
• The third line contains an integer
• The next Q lines contain the query array, where Q represents the number of queries.

Output format

For each test case, print Q space-separated integers representing the maximum number of toys you can purchase in a new line.

Constraints
1<=T<=10
1<=N<=10^5
1<=A[i] <=10^6
1<=Q<=10^4
1<=C<=10^9
0<=K<=10
1<=Query[i][j] <=N for every j>1

Sample Input
1
10
7 3 6 8 2 1 4 9 5 10
4
10 3 3 5

Sample Output
3 5 5 10