Module assignment: Exam results ranking

Why this assignment

This assignment brings the whole module together. You will read records from input, sort them with a comparator that has two keys, give each record a rank that handles ties, and compute a result from the whole list. Each of those steps appeared in one lesson of this module. Here you put them in one program, which is the way they show up in real work.

You will need the ideas from lesson 1 to reason about the cost of your loops, from lesson 2 to keep ties in a sensible order, from lesson 3 to see why a fast sort is worth using, and from lesson 4 to write the comparator. Read the spec carefully, because the output format is strict. A program that gets every number right but prints the lines in the wrong format will not pass.

Plan on about an hour. Write the code in pieces: read the input, compute the totals, sort, print the ranks, then add the average line. Test after each piece. Do not try to write the whole program in one pass.

The story

A school's exam office has a file with one line for each student. Each line has the student's name and three test marks out of 100. The office wants a ranking report. The head teacher reads the report to decide which students to call in for extra help, and to decide who receives the class prize. Your job is to write the program that produces the report.

The report has two parts. The first part is a ranked list of students, from the highest total to the lowest. The second part is one line that names the students who are doing better than the class average. The ranking must follow the school's rules for ties, which are explained below.

The school does not want you to use decimals or round anything. Every number in the report is a whole number, and the average comparison must be exact. That rule matters, and the hidden tests check it with inputs designed to catch rounding mistakes.

The input

The first line contains one integer, n. It is the number of students, and it satisfies 1 <= n <= 1,000.

Each of the next n lines describes one student. The line has four tokens separated by single spaces.

1. The student's name, made only of lowercase letters from a to z. A name has between 1 and 10 letters.
2. The first test mark, an integer from 0 to 100.
3. The second test mark, an integer from 0 to 100.
4. The third test mark, an integer from 0 to 100.

Names can repeat, and two students can have the same marks. You can assume the input is well formed. You do not need to check for bad input.

The output

The output has n ranking lines, followed by one average line. Print nothing else.

The ranking lines

Each ranking line has three parts separated by single spaces: the rank, the name and the total. The total is the sum of the three marks. The lines are in ranking order, which is decided by these rules.

• The student with the highest total comes first.
• Students with equal totals are ordered by name, from A to Z. Names are lowercase, so the normal string order is correct.
• Ranks use competition ranking. Students with the same total share the same rank. The next rank after a tie skips the numbers the tied students used. So if three students tie for first, they are all rank 1, and the next student is rank 4.

Here is an example of competition ranking. Four students have totals 270, 240, 240 and 210. The output ranks are 1, 2, 2 and 4. The 210 student is rank 4 because there were three students ahead of them, not two.

The average line

The last line starts with the words above average:. It then lists, in ranking order, the names of the students whose total is strictly greater than the class average total. If nobody qualifies, the line ends with the word none.

The class average is the sum of all totals divided by n. Do not compute it with floating-point numbers. Instead, compare each student's total multiplied by n with the sum of all totals. A student qualifies when total * n is greater than the sum. This is exact, because it uses only whole numbers, and it avoids the rounding errors that decimal division causes.

Examples

The examples below are the ones the grader also checks, with the exact expected output. Type the input into your program and compare the output line by line.

Example 1

Input:

5
asha 80 90 70
ravi 90 90 90
meera 60 70 80
kiran 90 80 70
dev 80 90 70

Output:

1 ravi 270
2 asha 240
2 dev 240
2 kiran 240
5 meera 210
above average: ravi

The totals are 240, 270, 210, 240 and 240. Their sum is 1,200, and n is 5, so a student qualifies when the total times 5 is more than 1,200. That means a total above 240, which only Ravi has. The three students with 240 share rank 2, and Meera with 210 is rank 5.

Example 2

Input:

3
zoe 100 100 100
yan 50 50 50
bo 50 50 50

Output:

1 zoe 300
2 bo 150
2 yan 150
above average: zoe

The totals are 300, 150 and 150. The sum is 600, and the average is 200. Only Zoe is above 200. Bo and Yan tie on 150, so they are ordered by name: Bo comes before Yan.

Example 3

Input:

1
sam 0 0 0

Output:

1 sam 0
above average: none

With one student the average equals that student's total, so nobody is strictly above it. This case checks that your program handles n equal to 1 and that it does not confuse "equal to the average" with "above the average".

Example 4

Input:

4
lee 60 60 60
mia 50 70 60
kai 90 0 0
obi 60 60 60

Output:

1 lee 180
1 mia 180
1 obi 180
4 kai 90
above average: lee mia obi

Three students tie on 180, so they all have rank 1, and Kai with 90 is rank 4, not rank 2. The sum is 630 and n is 4, so the threshold is a total above 157.5. The three 180 students qualify, and Kai does not. A floating-point average would give the same answer here, but the hidden tests include cases where it would not.

Requirements checklist

Use this checklist as you work. Tick each box when you have tested the item, not when you think you have written it.

• The program reads n, then exactly n lines, each with a name and three marks.
• Each total is the sum of the three marks, computed as an integer.
• The sum of all totals is computed as an integer, and used for the average.
• Students are sorted with std::sort (or std::stable_sort) and a comparator.
• The comparator uses a two-part rule: total descending, then name ascending.
• Ranks follow competition ranking, so tied students share a rank and the next rank skips.
• Each ranking line has the rank, the name and the total, separated by single spaces.
• The average line uses total * n > sum and never a floating-point number.
• The average line prints above average: none when no student qualifies.
• The average line lists the qualifying names in ranking order, separated by single spaces.
• The program handles n equal to 1 and all students tied.
• The program compiles with g++ -std=c++17 -Wall -Wextra and gives no warnings.
• The code has a comment that gives the time complexity of the sort, in terms of n.
• The program passes all four examples above, character for character.

Grading rubric

The grade depends on what the program does on the hidden test cases, which include the examples. Each level below describes what a solution at that level looks like.

60 percent. The program reads the input and prints one line per student with the correct total. The lines are sorted by total from highest to lowest, with ties broken by name. The ranks are simple positions, such as 1 to n, rather than competition ranks. The average line may be missing or may use a wrong rule. The program works on the first example but may fail on ties in the total.

80 percent. The program handles competition ranking correctly, so tied students share a rank and the next rank skips. The average line is printed, and it lists the right students for typical inputs, but it may fail on inputs where the average is a whole number or where it has a fraction. The program handles n equal to 1 without a crash.

100 percent. The program passes every example and every hidden test. It uses integer arithmetic for the average, so there is no floating-point rounding. The comparator follows the two-part rule and is strict. The code is organised into clear steps, with names that explain each step. The comment states the time complexity of the sort and of the whole program. The program has no warnings under -Wall -Wextra.

Two points separate the top two levels from the rest. The first is the average. Many solutions use double and then compare, and those solutions pass the examples but fail the hidden tests that have exact averages. The second is the rank. Many solutions give every student a unique number, which ignores the tie rule. Both are easy to fix once you know to look.

Step-by-step hints

Work through the steps in order, and try each one before you open the next hint. The hints are hidden so you can think first.

Stretch extension (optional, not graded)

Once the main program passes all tests, you can extend it. The extension is optional, and it does not change the required output.

Add a second mode. If the first line contains two numbers, n and m, print only the top m ranking lines, but still compute the average line from all n students. The first line becomes n m, with m at most n. Keep the average line exactly as before. The point of the extension is to practise separating the step that prints from the step that computes.

Also write a version that uses std::stable_sort in place of std::sort, and check whether the ranking changes. Explain why it does or does not. The comparator already breaks every tie by name, so the stable and unstable versions should give the same output. Explain what would change if you removed the name rule and sorted by total alone.

Submission and self-check

Write your program as one file called main.cpp. The file must compile with g++ -std=c++17 -Wall -Wextra -o main main.cpp and run with input from standard input. Test it with the four examples in this lesson before you submit it.

Before you submit, answer these questions in your own words, as if an interviewer had asked them.

1. Which sort did you use, and what is its time complexity on your input?
2. Why does your comparator use > and < rather than >= and <=?
3. How does your rank logic give 1, 2, 2, 4 instead of 1, 2, 3, 4?
4. Why does total * n > sum give the same answer as comparing the total with the average, but without rounding?
5. What would your program print for an input where every student has the same total? Work it out before you run it.

Reference solution

The reference solution is hidden. Try the assignment first, and use it only to check your answer or to see a clean structure after you finish.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
struct Student {
    string name;
    long long total;
};
 
int main() {
    int n;
    cin >> n;
    vector<Student> s(n);
    long long sum = 0;
    for (auto& st : s) {
        int a, b, c;
        cin >> st.name >> a >> b >> c;
        st.total = a + b + c;
        sum += st.total;
    }
 
    // Highest total first. Equal totals are sorted by name, A to Z.
    sort(s.begin(), s.end(), [](const Student& x, const Student& y) {
        if (x.total != y.total) return x.total > y.total;
        return x.name < y.name;
    });
 
    // Competition ranking: equal totals share a rank, and the next rank skips.
    int rank = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || s[i].total != s[i - 1].total) rank = i + 1;
        cout << rank << " " << s[i].name << " " << s[i].total << "\n";
    }
 
    // Above average: total * n > sum avoids floating point.
    vector<string> above;
    for (auto& st : s) {
        if (st.total * n > sum) above.push_back(st.name);
    }
    cout << "above average:";
    if (above.empty()) cout << " none";
    for (auto& nm : above) cout << " " << nm;
    cout << "\n";
    return 0;
}