# ABOVEAVG Editorial

Setter: Utkarsh Gupta
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

1278

None

# PROBLEM:

There are N students in a class. Recently, an exam on Advanced Algorithms was conducted with maximum score M and minimum score 0. The average score of the class was found out to be exactly X.

Given that a student having score strictly greater than the average receives an A grade, find the maximum number of students that can receive an A grade.

# EXPLANATION:

Let us look at the two cases for this problem:

• X=M: Here it implies that every single student has scored M marks and since no student can score more than M marks. Thus in this case no student would receive A grade.
• X < M: Let us take a variable sum as the sum of marks of all students. Then
sum = N \times X

Now to maximise students who score more than average marks we assign (X+1) marks to as many students as possible, which would be our answer.

answer = \lfloor \frac{sum}{X+1} \rfloor

# TIME COMPLEXITY:

O(1), for each test case.

# SOLUTION:

In the problem, it was not mentioned that the scores of the student must be integer. Also, the sample test cases passed the solutions which assumed the solutions to include non-integer scores.

3 Likes

So true man! Was stuck for good time in this…

I don’t get it. Why would answer be the floor of n*x/(x+1) ? I understand we are trying to maximise but I can’t make the connection between that and the mathematical expression. Can someone please elaborate?

5 Likes

Average = Sum of score/ N.
So sum of score = NX
Number the persons from 1 to N. Start assigning them (X+1) scores from 1 to N. What’s the maximum number of person you can assign X+1 exactly floor(N
X/(X+1)). After that you’ll be left with N*X mod (X+1) score which is less than X+1 which it doesn’t to whom you give

1 Like

I Know the approach I used in below code is not optimized but still I want to know why the last teste case is failling ?

#include <iostream>
using namespace std;

int main() {

int T ; cin>>T;
while(T--)
{
double n ,m ,x; cin>>n>>m>>x;

if(m==x)
{
cout<<0<<endl;
continue;
}

for(int i=1 ; i<=n ; i++)
{
if(((x+1)*(n-i))/n<=x)
{
cout<<n-i<<endl;
break;
}
}
}

return 0;
}