Initially i was not even able to understand this question, but after understanding it a little bit i had tried to solve it , but the code is only passing a single test case and fails rest of all. Kindly help me in understanding this problem.
Winning CB Scholarship
Hello @mvermav19,
According to the question,
- Initially there are N students and M coupons
- 100% wavier is given to those who have at least X coupons (good students)
- Bad students must give Y coupons to take admission
So, let’s form an equation, If there are k good students then (N - k) students must have performed bad.
Initial Coupons - k*X + (N - k)*Y >= 0
Initial Coupons = M
You, just need to solve this equation by maximizing k such that k <= N
Hint: You can apply binary search for optimal k
why we had done this? I’m not able to understand this part.
Means why it should be greater than 0??
Is it the total number of coupons used??
Yes, it is the total number of coupons.
Initial Coupons - k*X + (N - k)*Y >= 0
Initially, total coupons are M, now for each student who performed badly will increase the total coupons by Y.
who perform badly in the admission tests, need to pay additional amount equivalent to Y discount coupons
Similarly, for each good student, the coupons will decrease by X.
A student will get 100% waiver if he gets X discount coupons.
Combine all the statements,
Total Coupons = M - (no. of good students)*X + (no. of bad students)*Y
If we let the number of good students be k then the number of bad students = N - k.
Can you please help me with the code?
I’m not able to understand this approach means like how to utilize it into the code?
int n,m,x,y;
cin>>n>>m>>x>>y;
int start = 1, end = n, good = 0;
while(start <= end){
int mid = (start + end)/2;
long int eqn = m - mid*(long int)x + (n-mid)*(long int)y;
if(eqn >= 0){
good = mid;
start = mid + 1;
}else{
end = mid - 1;
}
}
cout<<good<<endl;@mvermav19,
Sorry, I sended the wrong code,
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m, x, y;
cin >> n >> m >> x >> y;
int start = 1, end = n, good = 0;
while (start <= end)
{
int mid = (start + end) / 2;
long long int eqn = m - mid * (long long int)x + (n - mid) * (long long int)y;
if (eqn >= 0)
{
good = mid;
start = mid + 1;
}
else
{
end = mid - 1;
}
}
cout << good << endl;
return 0;
}I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.