Online Assessment Problem

Revision en1, by lkjhgfertyul, 2023-01-25 18:37:36

Problem Statement:
There is an array "cost" of length n, cost[i] is the cost of i'th robot and an array "A" of length n, A[i] is the number written on the i'th robot, you are also given an integer K which is the amount you have. You can buy a robot only if cost of that robot is less than or equal to the remaining amount you have(obviously).
Suppose you buy x robots with indices i1, i2, i3 ... ix then you will get one gift card for each i such that A[i] >= x (i belongs to indices of robots you purchased). Calculate the maximum number of gift cards you can get.

Constraints
1<= n <= 100
1<= K <= 1e9
1<= cost[i] <= 1e4
1<= A[i] <= n

Sample Input
5 300 <-- (n, K)
4 5 4 3 2 <-- (cost)
120 150 80 90 100 <-- (A)

Sample Output
2

Explanation
Buy robots with indices 3,4,5 cost 270(<=300) and you will get 2 gift cards for robots 4 and 5


I was thinking of some knapsack type approach but was not able to get a solution. You can comment your solution or post a link to a similar problem with solution, thanks.

Tags dp, knapsack, online assessment

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lkjhgfertyul 2023-01-25 18:37:36 1149 Initial revision (published)