O número de um cartão de registro do PAT é composto por quatro partes:

• O primeiro caractere indica o nível do teste: 'T' para o nível superior, 'A' para avançado e 'B' para básico.
• Do segundo ao quarto caractere: o número do local de teste, variando de 101 a 999.
• Do quinto ao décimo caractere: a data do teste, no formato 'aammdd'.
• Do décimo primeiro ao décimo terceiro caractere: o número do candidato, variando de 000 a 999.

Dado um conjunto de números de cartão e as respectivas pontuações, deve-se responder a várias consultas estatísticas.

Especificação de Entrada

Cada arquivo de entrada contém um caso de teste. A primeira linha contém dois inteiros positivos N (≤ 10000) e M (≤ 100), o número de cartões e o número de consultas, respectivamente.

As N linhas seguintes contêm, cada uma, o número do cartão e a pontuação do candidato (inteiro entre 0 e 100), separados por espaço.

Depois, há M linhas, cada uma com uma consulta no formato 'Tipo Termo', onde:

• Tipo 1: listar todos os candidatos de um determinado nível, em ordem decrescente de pontuação. O Termo é a letra que especifica o nível.
• Tipo 2: listar o número total de candidatos e a soma das pontuações para um determinado local de teste. O Termo é o número do local.
• Tipo 3: listar, para cada local, o número total de candidatos em uma determinada data de teste. O Termo é a data no formato 'aammdd'.

Especificação de Saída

Para cada consulta, imprima primeiro a linha 'Caso #: consulta', onde # é o índice do caso (começando em 1) e consulta é a entrada da consulta. Em seguida, produza a saída conforme o tipo:

• Tipo 1: o formato é o mesmo da entrada, ou seja, 'NúmeroCartão Pontuação'. Em caso de empate na pontuação, ordene em ordem alfabética crescente dos números de cartão (a unicidade dos números de cartão é garantida).
• Tipo 2: produza 'Nt Ns' onde Nt é o número total de candidatos e Ns é a soma das pontuações.
• Tipo 3: produza 'Local Nt' onde Local é o número do local e Nt é o número total de candidatos nesse local. A saída deve estar em ordem decrescente de Nt, ou em ordem crescente do número do local em caso de empate.

Se o resultado de uma consulta for vazio, simplesmente imprima 'NA'.

Exemplo de Entrada

8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999

Exemplo de Saída

Caso 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Caso 2: 2 107
3 260
Caso 3: 3 180908
107 2
123 2
102 1
Caso 4: 2 999
NA

Solução em C++

Abaixo, uma implementação em C++ que resolve o problema. O código utiliza estruturas de dados da STL (vector, map) e funções de ordenação personalizadas para eficiência.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

struct Candidato {
    string identificador;
    int pontuacao;
};

bool compararPorPontuacaoEId(const Candidato &a, const Candidato &b) {
    if (a.pontuacao != b.pontuacao) return a.pontuacao > b.pontuacao;
    return a.identificador < b.identificador;
}

bool compararPorContagemELocal(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}

int main() {
    int totalCandidatos, totalConsultas;
    cin >> totalCandidatos >> totalConsultas;
    vector<Candidato> listaCandidatos(totalCandidatos);
    for (int i = 0; i < totalCandidatos; ++i) {
        cin >> listaCandidatos[i].identificador >> listaCandidatos[i].pontuacao;
    }

    for (int consulta = 0; consulta < totalConsultas; ++consulta) {
        int tipo;
        string termo;
        cin >> tipo >> termo;
        cout << "Caso " << consulta + 1 << ": " << tipo << " " << termo << endl;

        if (tipo == 1) {
            vector<Candidato> resultado;
            for (const auto &candidato : listaCandidatos) {
                if (candidato.identificador[0] == termo[0]) {
                    resultado.push_back(candidato);
                }
            }
            if (resultado.empty()) {
                cout << "NA" << endl;
            } else {
                sort(resultado.begin(), resultado.end(), compararPorPontuacaoEId);
                for (size_t i = 0; i < resultado.size(); ++i) {
                    cout << resultado[i].identificador << " " << resultado[i].pontuacao;
                    if (i != resultado.size() - 1) cout << endl;
                }
            }
        } else if (tipo == 2) {
            int contagem = 0, somaPontuacoes = 0;
            for (const auto &candidato : listaCandidatos) {
                if (candidato.identificador.substr(1, 3) == termo) {
                    ++contagem;
                    somaPontuacoes += candidato.pontuacao;
                }
            }
            if (contagem == 0) {
                cout << "NA" << endl;
            } else {
                cout << contagem << " " << somaPontuacoes << endl;
            }
        } else if (tipo == 3) {
            map<int, int> contagemPorLocal;
            for (const auto &candidato : listaCandidatos) {
                if (candidato.identificador.substr(4, 6) == termo) {
                    int local = stoi(candidato.identificador.substr(1, 3));
                    ++contagemPorLocal[local];
                }
            }
            if (contagemPorLocal.empty()) {
                cout << "NA" << endl;
            } else {
                vector<pair<int, int>> locais(contagemPorLocal.begin(), contagemPorLocal.end());
                sort(locais.begin(), locais.end(), compararPorContagemELocal);
                for (size_t i = 0; i < locais.size(); ++i) {
                    cout << locais[i].first << " " << locais[i].second;
                    if (i != locais.size() - 1) cout << endl;
                }
            }
        }
        if (consulta != totalConsultas - 1) cout << endl;
    }
    return 0;
}