Dada una pila con capacidad máxima M. Se empujan N números en el orden 1, 2, 3, ..., N y se extraen aleatoriamente. Se debe determinar si una secuencia dada es una posible secuencia de extracción de la pila. Por ejemplo, si M es 5 y N es 7, se puede obtener 1,2,3,4,5,6,7 de la pila, pero no 3,2,1,7,5,6,4.

Especificación de Entrada:

Cada archivo de entrada contiene un caso de prueba. Para cada caso, la primera línea contiene 3 números (todos no más de 1000): M (capacidad máxima de la pila), N (longitud de la secuencia de empuje), y K (número de secuencias de extracción a verificar). Luego siguen K líneas, cada una contiene una secuencia de extracción de N números. Todos los números en una línea están separados por un espacio.

Especificación de Salida:

Para cada secuencia de extracción, imprima en una línea "SÍ" si es una posible secuencia de extracción de la pila, o "NO" si no.

Ejemplo de Entrada:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Ejemplo de Salida:

SÍ
NO
NO
SÍ
NO

Implementación:

A continuación se muestra una implementación en C++ que simula las operaciones de la pila para verificar las secuencias. Se utiliza una pila auxiliar para empujar números en orden y comparar con la secuencia de extracción dada, verificando que la capacidad no se exceda.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int capacidadMaxima, longitudSecuencia, numeroSecuencias;
    cin >> capacidadMaxima >> longitudSecuencia >> numeroSecuencias;

    vector<int> numerosEmpujar(longitudSecuencia + 1);
    for (int idx = 1; idx <= longitudSecuencia; idx++) {
        numerosEmpujar[idx] = idx;
    }

    for (int caso = 0; caso < numeroSecuencias; caso++) {
        stack<int> pilaAuxiliar;
        vector<int> secuenciaObjetivo(longitudSecuencia + 1);
        for (int pos = 1; pos <= longitudSecuencia; pos++) {
            cin >> secuenciaObjetivo[pos];
        }

        int siguienteNumero = 1;
        int indiceObjetivo = 1;
        bool esValido = true;

        while (indiceObjetivo <= longitudSecuencia) {
            if (pilaAuxiliar.size() > capacidadMaxima) {
                esValido = false;
                break;
            }

            if (!pilaAuxiliar.empty() && pilaAuxiliar.top() == secuenciaObjetivo[indiceObjetivo]) {
                pilaAuxiliar.pop();
                indiceObjetivo++;
            } else if (siguienteNumero <= longitudSecuencia) {
                pilaAuxiliar.push(numerosEmpujar[siguienteNumero]);
                siguienteNumero++;
            } else {
                esValido = false;
                break;
            }
        }

        cout << (esValido ? "SÍ" : "NO") << endl;
    }

    return 0;
}