[Solution] Lazy Salesman solution codechef

Lazy Salesman solution codechef – Ved is a salesman. He needs to earn at least WW rupees in NN days for his livelihood. However, on a given day ii (1iN1≤i≤N), he can only earn AiAi rupees by working on that day.

Ved, being a lazy salesman, wants to take as many holidays as possible. It is known that on a holiday, Ved does not work and thus does not earn anything. Help maximize the number of days on which Ved can take a holiday.

It is guaranteed that Ved can always earn at least WW rupees by working on all days.

Lazy Salesman solution codechef

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains two integers NN and WW – the size of the array AA and the money Ved has to earn in those NN days.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the money which Ved can earn on each day.

Output Format

For each test case, output the maximum number of holidays Ved can take.

Lazy Salesman solution codechef

  • 1T1001≤T≤100
  • 1W100001≤W≤10000
  • 1N1001≤N≤100
  • 1Ai1001≤Ai≤100
  • It is guaranteed that Ved can always earn at least WW rupees by working on all days.

Sample Input 1 

5 10
3 2 6 1 3
4 15
3 2 4 6
6 8
9 12 6 5 2 2

Sample Output 1 


Lazy Salesman solution codechef

Test case-1: Ved can work on 22-nd, 33-rd and 55-th day earning 2+6+3=112+6+3=11 rupees W≥W rupees. Thus he can take 22 holidays on the 11-st and the 44-th day.

Test case-2: Ved has to work on all days to earn W≥W rupees. Thus he can not take any holidays.

Test case-3: Ved can work on 22-nd day earning 1212 rupees W≥W rupees. Thus he can take holiday on the remaining days.

Leave a Comment