Fuente: Cuarta Edición del Concurso Provincial de la Copa Lanqiao, Grupo C++ A/B

Categoría de algoritmo: Ordenamiento, Simulación

Descripción del problema

Una agencia de seguridad emitió ciertos vales que deben ser recuperados al final del año. Cada vale tiene un ID único. Todos los IDs del año son consecutivos, pero el número de inicio se selecciona aleatoriamente. Por descuido del personal, al registrar los IDs ocurrió un error: un ID se perdió (falta) y otro ID se repitió (duplicado). Tu tarea es ecsribir un programa para encontrar el ID faltante y el ID duplicado. Se asume que el ID faltante no es ni el mínimo ni el máximo de la secuencia.

Formato de entrada

La primera línea contiene un entero N, que indica que hay N líneas de datos a continuación. Las siguientes N líneas contienen varios enteros positivos (no más de 100 por línea, cada entero no mayor a 100000), separados por espacios, representando los IDs.

Formato de salida

El programa debe imprimir una línea con dos enteros m y n separados por un espacio. Donde m es el ID faltante y n es el ID duplicado.

Rango de datos

1 ≤ N ≤ 100

Ejemplo de entrada

2
5  6  8  11  9
10  12  9

Ejemplo de salida

7 9

Soluciones en C++

Enfoque 1: Procesamiento de cadenas y ordeanmiento

Leemos todas las líneas como cadenas, extraemos los números usando stringstream, los almacenamos en un arreglo y luego lo ordenamos. Después, recorremos el arreglo para detectar el faltante (diferencia ≥2) y el duplicado (diferencia 0).

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>

using namespace std;

const int MAX_SIZE = 100010;
int datos[MAX_SIZE];
int total = 0;

int main() {
    int lineas;
    cin >> lineas;

    string linea;
    getline(cin, linea); // ignorar el salto de línea después del número

    while (lineas--) {
        getline(cin, linea);
        stringstream ss(linea);
        int valor;
        while (ss >> valor) {
            datos[total++] = valor;
        }
    }

    sort(datos, datos + total);

    int faltante = 0, duplicado = 0;
    for (int i = 1; i < total; ++i) {
        if (datos[i] - datos[i-1] >= 2) {
            faltante = datos[i] - 1;
        } else if (datos[i] == datos[i-1]) {
            duplicado = datos[i];
        }
    }

    cout << faltante << " " << duplicado << endl;
    return 0;
}

Enfoque 2: Conteo de frecuencias (bucket sort)

En lugar de ordenar, contamos cuántas veces aparece cada ID usando un arreglo de frecuencias. Luego recorremos desde el mínimo hasta el máximo para encontrar el faltante (frecuencia 0) y el duplicado (frecuencia 2).

#include <iostream>

using namespace std;

const int MAX_VALOR = 100010;
int frecuencia[MAX_VALOR] = {0};

int main() {
    int lineas;
    cin >> lineas;

    int valor;
    int min_val = MAX_VALOR, max_val = -1;

    while (lineas--) {
        while (cin >> valor) {
            frecuencia[valor]++;
            if (valor < min_val) min_val = valor;
            if (valor > max_val) max_val = valor;
        }
    }

    int faltante = 0, duplicado = 0;
    for (int i = min_val; i <= max_val; ++i) {
        if (frecuencia[i] == 0) faltante = i;
        else if (frecuencia[i] == 2) duplicado = i;
    }

    cout << faltante << " " << duplicado << endl;
    return 0;
}