lower_bound on map

Lab C++ Advanced 30 points

Store grade thresholds in a map<int, char>: 0→F, 50→D, 60→C, 70→B, 85→A. For each score use upper_bound to find the right grade.

Input

n, then n scores.

Output

n lines.

Example

Input

Output

F
D
C
A
A

Sample input available Sample output available

Editor

C++

Hints

upper_bound(k) points to the first key > k; the entry before it is the one that applies.

Solution explanation

Ordered maps answer "which range contains this value?" in O(log n).

Show solution

#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main() {
    map<int, char> grades = {{0, 'F'}, {50, 'D'}, {60, 'C'}, {70, 'B'}, {85, 'A'}};
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        auto it = prev(grades.upper_bound(score));
        cout << it->second << "\n";
    }
    return 0;
}

Output

Answer