Se necesita implementar un sistema de recomendación muy básico que predice la preferencia de un usuario por un ítem según la cantidad de veces que lo ha consultado. Dado el histórico de accesos (lista de identificadores de ítems), el sistema debe mostrar, para cada nueva consulta, los K ítems más frecunetes hasta ese momento, ordenados de mayor a menor frecuencia. En caso de empate en la frecuencia, se ordenan por idantificador ascendente.

Formato de entrada

La primera línea contiene dos enteros positivos: N (≤ 50000), número total de consultas, y K (≤ 10), número máximo de recomendaciones. La segunda línea contiene los identificadores de los ítems acedidos (numerados de 1 a N). Todos los números separados por espacios.

Formato de salida

Para cada consulta (excepto la primera), se muestra una línea con el formato:

consulta: rec1 rec2 ... recK

donde consulta es el ítem actual y reci son los ítems recomendados. Se garantiza al menos una salida.

Ejemplo

Entrada:

12 3
3 5 7 5 5 3 2 1 8 3 8 12

Salida:

5: 3
7: 3 5
5: 3 5 7
5: 5 3 7
3: 5 3 7
2: 5 3 7
1: 5 3 2
8: 5 3 1
3: 5 3 1
8: 3 5 1
12: 3 5 8

Solución propuesta en C++

La implementación utiliza un conjunto ordenado (set) que almacena pares (frecuencia, id) con un comparador personalizado: frecuencia descendente y, en caso de igualdad, id ascendente. Se mantiene un arreglo de frecuencias actualizadas. Al leer cada consulta, primero se muestran los primeros K elementos del conjunto (si no es la primera), luego se actualiza la frecuencia del ítem: se elimina la entrada anterior del conjunto, se incrementa la frecuencia y se inserta la nueva entrada.

#include <cstdio>
#include <set>

using namespace std;

struct Elemento {
    int id;
    int freq;
    Elemento(int _id, int _freq) : id(_id), freq(_freq) {}
    bool operator<(const Elemento &otro) const {
        if (freq != otro.freq) return freq > otro.freq;
        return id < otro.id;
    }
};

int frecuencias[50005];
set<Elemento> conjunto;

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    
    for (int i = 0; i < N; ++i) {
        int item;
        scanf("%d", &item);
        
        if (i != 0) {
            printf("%d:", item);
            int cont = 0;
            for (auto it = conjunto.begin(); it != conjunto.end() && cont < K; ++it, ++cont) {
                printf(" %d", it->id);
            }
            printf("\n");
        }
        
        // Actualizar frecuencia
        conjunto.erase(Elemento(item, frecuencias[item]));
        frecuencias[item]++;
        conjunto.insert(Elemento(item, frecuencias[item]));
    }
    
    return 0;
}

La complejidad es O(N log N) en el peor caso, suficiente para los límites del problema. El conjunto garantiza que las recomendaciones se obtengan en orden correcto sin necesidad de ordenar cada vez.