Solución a Problemas de Programación Competitiva en C++: Algoritmos Greedy, DP y Grafos

Recopilación de soluciones optimizadas e implementadas en C++ para diversos ejercicios clásicos de programación competitiva, abarcando técnicas como ordenamiento voraz (greedy), programación dinámica (DP), recorridos en grafos (DFS y BFS) y teoría de números.

A - Shoemaker's Problem

Enfoque: Algoritmo voraz (greedy) mediante ordenación personalizada basada en la relación costo/beneficio entre la multa y el tiempo requerido.

#include <iostream>
#include <algorithm>
using namespace std;

int tiempo[1000];
int multa[1000];
int trab[1000];

bool comp(int a, int b) {
    double res1 = (double)multa[a] / tiempo[a];
    double res2 = (double)multa[b] / tiempo[b];
    if (res1 == res2)
        return a < b;
    return res1 > res2;
}

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

    while (casos--) {
        int N;
        cin >> N;

        for (int i = 0; i < N; i++) {
            cin >> tiempo[i] >> multa[i];
            trab[i] = i;
        }
        sort(trab, trab + N, comp);

        for (int i = 0; i < N; i++) {
            if (i > 0) {
                cout << " ";
            }
            cout << trab[i] + 1;
        }
        cout << "\n";

        if (casos) cout << "\n";
    }
    return 0;
}

A - Cutting Sticks

Enfoque: Programación dinámica de intervalos (similar a la multiplicación encadenada de matrices) para minimizar el costo total de corte.

#include <iostream>
#include <climits>

using namespace std;

int main() {
    int l;
    while (cin >> l && l != 0) {
        int n;
        cin >> n;
        int cortes[55];
        cortes[0] = 0;

        for (int i = 1; i <= n; i++)
            cin >> cortes[i];
        cortes[n + 1] = l;
        int dp[55][55];

        for (int i = 0; i <= n + 1; i++)
            for (int j = 0; j <= n + 1; j++)
                dp[i][j] = 0;

        for (int len = 2; len <= n + 1; len++) {
            for (int i = 0; i + len <= n + 1; i++) {
                int j = i + len;
                dp[i][j] = INT_MAX;

                for (int k = i + 1; k < j; k++) {
                    int costo = dp[i][k] + dp[k][j] + (cortes[j] - cortes[i]);
                    if (costo < dp[i][j])
                        dp[i][j] = costo;
                }
            }
        }

        cout << "The minimum cutting is " << dp[0][n + 1] << "." << endl;
    }

    return 0;
}

B - The Twin Towers

Enfoque: Cálculo de la subsecuencia común más larga (LCS, Longest Common Subsequence) utilizando una tabla bidimensional de programación dinámica.

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

int main() {
    int N1, N2;
    int c = 1;
    while (true) {
        cin >> N1 >> N2;
        if (N1 == 0 && N2 == 0) {
            break;
        }

        vector<int> A(N1), B(N2);
        for (int i = 0; i < N1; i++) {
            cin >> A[i];
        }
        for (int j = 0; j < N2; j++) {
            cin >> B[j];
        }
        // dp (N1 + 1) x (N2 + 1)
        vector<vector<int>> dp(N1 + 1, vector<int>(N2 + 1, 0));
        // tabla
        for (int i = 1; i <= N1; i++) {
            for (int j = 1; j <= N2; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        cout << "Twin Towers #" << c++ << "\n";
        cout << "Number of Tiles : " << dp[N1][N2] << "\n\n";
    }
    return 0;
}

A - Vertex

Enfoque: Búsqueda en profundidad (DFS) en grafos dirigidos para identificar nodos inalcanzables a partir de un vértice dado.

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

vector<int> ady[101];
bool visitado[101];
int n;

void dfs(int u) {
    visitado[u] = true;
    for (int v : ady[u]) {
        if (!visitado[v]) dfs(v);
    }
}

int main() {
    while (true) {
        cin >> n;
        if (n == 0) break;
        for (int i = 1; i <= n; i++) {
            ady[i].clear();
        }

        while (true) {
            int a;
            cin >> a;

            if (a == 0) break;
            while (true) {
                int b;
                cin >> b;
                if (b == 0) break;
                ady[a].push_back(b);
            }
        }

        int cantidad;
        cin >> cantidad;

        while (cantidad--) {
            int inicio;
            cin >> inicio;

            for (int i = 1; i <= n; i++) visitado[i] = false;

            for (int v : ady[inicio]) {
                if (!visitado[v]) dfs(v);
            }
            vector<int> inaccesibles;
            for (int i = 1; i <= n; i++) {
                if (!visitado[i]) {
                    inaccesibles.push_back(i);
                }
            }
            cout << inaccesibles.size();
            for (int x : inaccesibles) cout << " " << x;
            cout << "\n";
        }
    }

    return 0;
}

B - Bombs! NO they are Mines!!

Enfoque: Búsqueda en anchura (BFS) en una matriz bidimensional con obstáculos para encontrar la ruta más corta.

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

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int main() {
    while (true) {
        int R, C;
        cin >> R >> C;
        if (R == 0 && C == 0) break;

        vector<vector<bool> > bomba(R, vector<bool>(C, false));
        vector<vector<int> > dist(R, vector<int>(C, -1));

        int filasConBombas;
        cin >> filasConBombas;

        while (filasConBombas--) {
            int fila, cantBombas;
            cin >> fila >> cantBombas;
            for (int i = 0; i < cantBombas; i++) {
                int col;
                cin >> col;
                bomba[fila][col] = true;
            }
        }
        int sr, sc, tr, tc;
        cin >> sr >> sc >> tr >> tc;

        queue<pair<int, int> > q;
        q.push(make_pair(sr, sc));
        dist[sr][sc] = 0;
        while (!q.empty()) {
            pair<int, int> front = q.front();
            q.pop();
            int r = front.first;
            int c = front.second;
            if (r == tr && c == tc) break;
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
                    !bomba[nr][nc] && dist[nr][nc] == -1) {

                    dist[nr][nc] = dist[r][c] + 1;
                    q.push(make_pair(nr, nc));
                }
            }
        }
        cout << dist[tr][tc] << "\n";
    }

    return 0;
}

A - How many zero's and how many digits?

Enfoque: Teoría de números usando la fórmula de Legendre para contar factores primos en fatoriales (ceros al final) y logaritmos para determinar la cantidad de dígitos en base B.

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

int main() {
    long long N;
    int B;

    while (cin >> N >> B) {
        int base = B;
        int primo[20], exponente[20];
        int totalPrimos = 0;

        for (int p = 2; p * p <= base; p++) {
            if (base % p == 0) {
                primo[totalPrimos] = p;
                exponente[totalPrimos] = 0;
                while (base % p == 0) {
                    exponente[totalPrimos]++;
                    base /= p;
                }
                totalPrimos++;
            }
        }

        if (base > 1) {
            primo[totalPrimos] = base;
            exponente[totalPrimos] = 1;
            totalPrimos++;
        }

        long long cerosFinales = LLONG_MAX;

        for (int i = 0; i < totalPrimos; i++) {
            long long contador = 0;
            long long p = primo[i];
            for (long long x = N; x > 0; x /= p)
                contador += x / p;
            cerosFinales = min(cerosFinales, contador / exponente[i]);
        }

        if (cerosFinales == LLONG_MAX)
            cerosFinales = 0;

        long double sumaLog = 0.0;
        for (int i = 1; i <= N; i++)
            sumaLog += log((long double)i);

        long long digitos;
        if (N <= 1)
            digitos = 1;
        else
            digitos = (long long)(sumaLog / log((long double)B) + 1e-12) + 1;

        cout << cerosFinales << " " << digitos << endl;
    }

    return 0;
}