Page Contents
Codechef Chef and Fixed Deposits MINFD Solution
Chef wants to make a purchase. For this, he needs XX gold coins, but he has none at the moment.
Chef has NN fixed deposits, the ithith of which is worth AiAi coins. He wants to open the minimum number of these deposits so that he has at least XX coins.
You have to tell Chef the minimum number of fixed deposits he must open in order to have XX coins, or say that this is impossible.
Input Format
- The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains two space-separated integers — NN and XX, as described in the statement.
- The second line of each test case contains NN space-separated integers — the ithith of which is AiAi.
Output Format
For each test case, output one line containing the answer — the minimum number of FDs Chef must open to have at least XX coins. If it is not possible for him to open FDs such that he has at least XX coins, output −1−1.
Constraints
- 1≤T,Ai,N≤1001≤T,Ai,N≤100
- 1≤X≤1041≤X≤104
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4 4 6 4 3 5 1 3 15 1 5 3 2 5 10 3 4 7 1 2 3 4
Sample Output 1
2 -1 1 2
Explanation
Test case 11: Chef can open the first and second FDs to get 4+3=74+3=7 coins.
Test case 22: No matter which FDs Chef opens, he cannot have ≥15≥15 coins, so the answer is −1−1.
Click Below for solution
Solution
Program: Chef and Fixed Deposits MINFD Solution in C++
#include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; for(int i=0;i<t;i++){ int n,x; int count=0; int sum=0; cin>>n>>x; bool f = false; int arr[n]; for(int j=0;j<n;j++){ cin>>arr[j]; } sort(arr,arr+n); for(int b=(n-1);b>=0;b--){ count++; sum = sum+arr[b]; if(sum>=x){ f = true; break; } } if(f){ cout<<count<<endl; } else{ cout<<"-1"<<endl; } } return 0; }
Program: Chef and Fixed Deposits MINFD Solution in Java
import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { Scanner inp = new Scanner(System.in); int t = inp.nextInt(); for(;t>0;t--){ int n,x; n = inp.nextInt(); x = inp.nextInt(); int arr[] = new int[n]; int sum = 0; for(int i=0;i<n;i++){ arr[i]=inp.nextInt(); sum+=arr[i]; } if(x>sum){ System.out.println(-1); }else{ Arrays.sort(arr); int count=0,ind=n-1; while(x>0){ x=x-arr[ind]; ind--; count++; } System.out.println(count); } } } }
Program: Chef and Fixed Deposits MINFD Solution in Python
for _ in range(int(input())): n,d=input().split() n=int(n) d=int(d) a=list(map(int,input().split())) a.sort() a.reverse() s=sum(a) if s>=d: if d in a: print("1") elif d<max(a): print("1") else: su=a[0] c=0 for i in range(1,n): if c==1: break su=su+a[i] if su==d or su>d: print(i+1) #print(a[i]) c=c+1 else: print("-1")
January Long Challenge 2022 Solution
- TCS Examination EXAMTIME Solution Codechef
- Chef and Fixed Deposits MINFD Solution Codechef
- Crying Colours CRYCOLR Solution Codechef
- Power Sum POWSUM Solution Codechef
- Sum and OR SUMANDOR Solution Codechef
- Tree Master TRMT Solution Codechef
- Array Partition ARRPART Solution Codechef
- Keplers Law KEPLERSLAW Solution
- Covid Spread COVSPRD Solution
- Prime in a binary string PINBS Solution
- Retrieve back the Array XORED Solution
- Chef and Riffles RIFFLES Solution
- Sequence Master MASTER Solution
- Generating Cycles GENECYC Solution