Problema de Secuencias de Entrada y Salida de Trenes en una Pila

Enumeración de Secuencias de Entrada y Salida

Dado un conjunto de números del 1 al n que entran en una pila en orden secuencial, se requiere generar las primeras 20 secuencias posibles de salida de la pila en orden lexicográfico.

Solución: Búsqueda en Profundidad (DFS)

Con el rango de datos dado, es factible utilizar una búsqueda en profundidad para enumerar todas las posibilidades.

Se deben mantener tres estados durante la exploración:

1. El estado actual de la pila.
2. El próximo número que está listo para entrar en la pila.
3. La secuencia de números que han salido de la pila.

Para cada paso, existen dos opciones:

1. Si la pila no está vacía, se puede sacar el elemento superior.
2. Si el próximo número a entrar no supera n, se puede introducir en la pila.

Si la longitud de la secuencia de salida alcanza n, se ha encontrado una posible solución. Al retroceder, es crucial restuarar los estados anteriores.

Para asegurar que las soluciones se generen en orden lexicográfico, primero se intenta sacar elementos de la pila y luego se introduce el siguiente número disponible.

#include <bits/stdc++.h>
using namespace std;

int n, tope = 0, contador = 20;
int pila[21];
vector<int> resultado;

void dfs(int siguiente) {
    if (!contador)
        return;
    if (resultado.size() == n) {
        contador--;
        for (int num : resultado)
            cout << num;
        cout << endl;
        return;
    }
    if (tope) {
        resultado.push_back(pila[tope--]);
        dfs(siguiente);
        pila[++tope] = resultado.back();
        resultado.pop_back();
    }
    if (siguiente <= n) {
        pila[++tope] = siguiente;
        dfs(siguiente + 1);
        tope--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    dfs(1);
    return 0;
}

Cálculo del Número de Secuencias de Salida

Dado un tren con n vagones numerados del 1 al n, donde cada vagon puede entrar o salir de una pila, se busca determinar cuántas secuencias diferentes de salida son posibles.

Solución: Números de Catalan + Factorización en Primos + Multiplicación de Precisión Arbitraria

La secuencia de entrada y salida puede representarse como una cadena de 0s y 1s, donde 0 representa la salida de un vagon y 1 su entrada. Para que una secuencia sea válida, en cualquier momento debe haber más 1s que 0s.

El número de secuencias válidas es un número de Catalan. Sin embargo, para valores grandes de n, se necesita calcular combinaciones sin tomar módulos, lo que implica factorizar en primos y multiplicar con precisión arbitraria.

Se utiliza la fórmula (C_{2n}^n) y se descompone en factores primos. Se calcula la potencia de cada primo en el numerador y el denominador, y se realiza la división.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 200001;
int primos[MAX], idx;
bool marcado[MAX];
int potencias[MAX];
map<int, int> factores;

void criba(int n) {
    for (int i = 2; i <= n; i++) {
        if (!marcado[i])
            primos[idx++] = i;
        for (int j = 0; j < idx && i * primos[j] <= n; j++) {
            marcado[i * primos[j]] = true;
            if (i % primos[j] == 0)
                break;
        }
    }
}

int contar_factores(int n, int p) {
    int res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}

vector<int> multiplicar(vector<int>& a, int b) {
    vector<int> c;
    int acarreo = 0;
    for (int i = 0; i < a.size() || acarreo; i++) {
        if (i < a.size())
            acarreo += a[i] * b;
        c.push_back(acarreo % 10);
        acarreo /= 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

int potencia(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp & 1)
            res *= base;
        exp >>= 1;
        base *= base;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    criba(2 * n);
    int x = n + 1;
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            factores[i]++;
            x /= i;
        }
    }
    if (x > 1)
        factores[x]++;
    for (int i = 0; i < idx; i++) {
        potencias[primos[i]] = contar_factores(2 * n, primos[i]) - 2 * contar_factores(n, primos[i]) - factores[primos[i]];
    }
    vector<int> resultado;
    resultado.push_back(1);
    for (int i = 0; i < idx; i++) {
        if (!potencias[primos[i]])
            continue;
        resultado = multiplicar(resultado, potencia(primos[i], potencias[primos[i]]));
    }
    for (int i = resultado.size() - 1; i >= 0; i--)
        cout << resultado[i];
    cout << endl;
    return 0;
}

Verificación de Secuencias de Salida Válidas

Dado un tamaño máximo M para una pila y una secuencia de N números del 1 al N que ingresan a la pila en orden, se deben verificar Q secuencias dadas para determinar si son válidas.

Solución: Simulación de la Pila O(n)

Para validar una secuencia, se simula el proceso de entrada y salida de los números en la pila. Un número solo puede salir si todos los números menores que él ya han entrado y salido.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, n, q;
    cin >> m >> n >> q;
    while (q--) {
        int pila[200001], tope = 0;
        int esperado = 1;
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
            pila[++tope] = num;
            while (tope && pila[tope] == esperado) {
                tope--;
                esperado++;
            }
            if (tope > m)
                break;
        }
        if (tope > m || tope)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}