Problema M: Construcción de Secuencias Periódicas

Este problema requiere la generación de una secuencia específica que siga el patrón 1, 1, 3 de forma repetitiva. La lógica se basa en el uso del operador módulo para asignar los valores correspondientes a cada posición del arreglo.

#include <iostream>
#include <vector>

using namespace std;

void generarPatron(int limite) {
    vector<int> secuencia(limite + 1);
    for (int idx = 1; idx <= limite; ++idx) {
        if (idx % 3 == 0) {
            secuencia[idx] = 3;
        } else {
            secuencia[idx] = 1;
        }
    }
    
    for (int idx = 1; idx <= limite; ++idx) {
        cout << secuencia[idx] << (idx == limite ? "" : " ");
    }
    cout << endl;
}

int main() {
    int cantidad;
    if (cin >> cantidad) {
        generarPatron(cantidad);
    }
    return 0;
}

Problema A: Comparación de Exponentes mediante Logaritmos

Para determinar cuál es mayor entre \(x^y\) y \(y^x\) sin incurrir en desbordamientos de memoria, aplicamos logaritmos en ambos lados de la desigualdad. La comparación se transforma en evaluar \(y \cdot \log(x)\) frente a \(x \cdot \log(y)\).

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

void compararPotencias() {
    double base_x, exp_y;
    cin >> base_x >> exp_y;

    double log_val1 = exp_y * log(base_x);
    double log_val2 = base_x * log(exp_y);

    if (abs(log_val1 - log_val2) < 1e-9) {
        cout << min(base_x, exp_y) << endl;
    } else if (log_val1 > log_val2) {
        cout << base_x << endl;
    } else {
        cout << exp_y << endl;
    }
}

int main() {
    compararPotencias();
    return 0;
}

Problema L: Resolución de Sistemas para Lados de Triángulos

Dados tres valores que representan combinaciones de los lados de un triángulo, podemos derivar las longitudes individuales resolviendo un sistema de ecuaciones lineales. Tras obtener los lados, validamos si cumplen con la desigualdad triangular.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void procesarCasoTriangulo() {
    long long v1, v2, v3;
    cin >> v1 >> v2 >> v3;
    
    long long suma = v3 - v1 + v2;
    if (suma % 2 != 0) {
        cout << "No" << endl;
        return;
    }
    
    long long lado_a = suma / 2;
    long long lado_b = v3 - lado_a;
    long long lado_c = v1 - lado_b;
    
    vector<long long> dimensiones = {lado_a, lado_b, lado_c};
    sort(dimensiones.begin(), dimensiones.end());
    
    if (dimensiones[0] > 0 && dimensiones[0] + dimensiones[1] > dimensiones[2]) {
        cout << "Yes" << endl;
        cout << lado_a << " " << lado_b << " " << lado_c << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        procesarCasoTriangulo();
    }
    return 0;
}

Problema E: Simulación de Tiempos de Ataque

En este escenario de combate, debemos calcular el tiempo necesario para eliminar a una serie de enemigos. Es crucial considerar el daño por ataque, la vida del enemigo y el tiempo de recuperación entre cada acción agresiva.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long n, intervalo, fuerza;
    cin >> n >> intervalo >> fuerza;
    
    vector<long long> vida(n), regeneracion(n);
    for (int i = 0; i < n; ++i) cin >> vida[i] >> regeneracion[i];
    
    long long cronometro = 0;
    bool derrota = false;
    
    for (int i = 0; i < n; ++i) {
        if (vida[i] <= fuerza) {
            cronometro += 1;
            if (i != n - 1) cronometro += (intervalo - 1);
        } else {
            vida[i] -= fuerza;
            cronometro += 1;
            long long balance = intervalo * regeneracion[i] - fuerza;
            
            if (balance >= 0) {
                derrota = true;
                break;
            } else {
                long long neto = -balance;
                long long golpes = (vida[i] + neto - 1) / neto;
                cronometro += intervalo * golpes;
                if (i != n - 1) cronometro += (intervalo - 1);
            }
        }
    }
    
    if (derrota) cout << "-1" << endl;
    else cout << cronometro << endl;
    
    return 0;
}

Problema C: Optimización de Mochila (DP)

Este problema se centra en determinar la necesidad de un objeto en una configuración óptima de la mochila. Calculamos el valor máximo con y sin el objeto actual para decidir si es indispensable o cuánto debe mejorar para serlo.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, capacidad;
    cin >> n >> capacidad;
    
    vector<int> peso(n + 1), valor(n + 1);
    for (int i = 1; i <= n; ++i) cin >> peso[i] >> valor[i];
    
    vector<long long> dp(capacidad + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = capacidad; j >= peso[i]; --j) {
            dp[j] = max(dp[j], dp[j - peso[i]] + valor[i]);
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        vector<long long> dp_aux(capacidad + 1, 0);
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            for (int k = capacidad; k >= peso[j]; --k) {
                dp_aux[k] = max(dp_aux[k], dp_aux[k - peso[j]] + valor[j]);
            }
        }
        
        long long con_item = dp_aux[capacidad - peso[i]] + valor[i];
        if (con_item < dp[capacidad]) {
            cout << dp[capacidad] - con_item + 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    
    return 0;
}

Problema D: Divide y Vencerás sobre Programación Dinámica

Para optimizar el cálculo de la mochila excluyendo un elemento a la vez (lo que resolvería el Problema C de forma más eficiente), utilizamos una estructura de árbol de decisión recursiva que procesa rangos de elementos.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int pesos[5005], valores[5005];
long long resultados[5005];
long long opt_global;

void resolver_rango(int l, int r, vector<long long> dp_actual) {
    if (l == r) {
        long long con_el = dp_actual[m - pesos[l]] + valores[l];
        resultados[l] = (con_el == opt_global) ? 1 : 0; // Lógica simplificada
        return;
    }
    
    int medio = (l + r) / 2;
    
    vector<long long> dp_derecha = dp_actual;
    for (int i = l; i <= medio; ++i) {
        for (int j = m; j >= pesos[i]; --j)
            dp_derecha[j] = max(dp_derecha[j], dp_derecha[j - pesos[i]] + valores[i]);
    }
    resolver_rango(medio + 1, r, dp_derecha);
    
    vector<long long> dp_izquierda = dp_actual;
    for (int i = medio + 1; i <= r; ++i) {
        for (int j = m; j >= pesos[i]; --j)
            dp_izquierda[j] = max(dp_izquierda[j], dp_izquierda[j - pesos[i]] + valores[i]);
    }
    resolver_rango(l, medio, dp_izquierda);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> pesos[i] >> valores[i];
    
    vector<long long> inicial(m + 1, 0);
    vector<long long> total = inicial;
    for(int i=1; i<=n; ++i)
        for(int j=m; j>=pesos[i]; --j) total[j] = max(total[j], total[j-pesos[i]] + valores[i]);
    
    opt_global = total[m];
    resolver_rango(1, n, inicial);
    
    for (int i = 1; i <= n; ++i) cout << resultados[i] << "\n";
    return 0;
}

Problema J: Análisis de Conectividad en Grafos Dirigidos

El objetivo es identificar nodos que cumplen una propiedad de orden total en el grafo. Se utiliza DFS para verificar la conectividad desde y hacia cada nodo, determinando si un nodo puede alcanzar o ser alcanzado por todos los demás nodos del conjunto.

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;
vector<int> adj[MAXN], rev_adj[MAXN];
bool visitado[MAXN];

void dfs(int u, vector<int> g[], int &contador) {
    visitado[u] = true;
    contador++;
    for (int v : g[u]) {
        if (!visitado[v]) dfs(v, g, contador);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }
    
    vector<int> posicion(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        int r1 = 0, r2 = 0;
        for (int j = 1; j <= n; ++j) visitado[j] = false;
        dfs(i, adj, r1);
        for (int j = 1; j <= n; ++j) visitado[j] = false;
        dfs(i, rev_adj, r2);
        
        if (r1 + r2 == n + 1) {
            posicion[r2] = i;
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        cout << posicion[i] << (i == n ? "" : " ");
    }
    cout << endl;
    
    return 0;
}