Problema C: Temporada de Fútbol

Este problema se resuelve aplicando el Máximo Común Divisor (MCD) y explorando un rango acotado de valores para determinar combinaciones viables. Se emplea el algoritmo de Euclides extendido para resolver ecuaciones diofánticas lineales, seguido de una iteración eficiente dentro de un límite calculado.

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

void gcd_extendido(ll a, ll b, ll &mcd, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        mcd = a;
    } else {
        gcd_extendido(b, a % b, mcd, y, x);
        y -= x * (a / b);
    }
}

int main() {
    ll total_partidos, puntos_necesarios, puntos_victoria, puntos_empate;
    scanf("%lld%lld", &total_partidos, &puntos_necesarios);
    scanf("%lld%lld", &puntos_victoria, &puntos_empate);

    if (total_partidos * puntos_victoria < puntos_necesarios) {
        printf("-1\n");
        return 0;
    }

    ll comun, coef_x, coef_y;
    gcd_extendido(puntos_victoria, puntos_empate, comun, coef_x, coef_y);

    if (puntos_necesarios % comun != 0) {
        printf("-1\n");
        return 0;
    }

    puntos_victoria /= comun;
    puntos_empate /= comun;
    puntos_necesarios /= comun;

    ll base = puntos_necesarios / puntos_victoria;
    ll victorias = -1, empates = -1;

    for (ll i = 0; i <= min(puntos_victoria, base); ++i) {
        ll residuo = puntos_necesarios - (base - i) * puntos_victoria;
        if (residuo % puntos_empate == 0) {
            victorias = base - i;
            empates = residuo / puntos_empate;
            break;
        }
    }

    if (victorias >= 0 && empates >= 0 && total_partidos - victorias - empates >= 0) {
        printf("%lld %lld %lld\n", victorias, empates, total_partidos - victorias - empates);
    } else {
        printf("-1\n");
    }
    return 0;
}

Problema D: Pintar el Árbol

Para este problema, se verifica que el árbol no tenga nodos con grado mayor o igual a 3; en caso contrario, no existe solución. Si el árbol es esencialmente una cadena, se aplica programación dinámica desde un nodo hoja. Se define un estado DP donde dp[u][color_padre][color_hijo] almacena el costo mínimo de colorear el subárbol enraizado en u, asumiendo que u tiene color_padre y su hijo inmediato tiene color_hijo, sujeto a restricciones de colores distintos entre nodos adyacentes.

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

struct EstadoDP {
    ll costo[4][4];
};

vector<int> adyacencia[100005];
int costo_color[4][100005];
EstadoDP memo[100005];
int grado[100005], asignacion[100005];

EstadoDP calcular_dp(int nodo, int padre) {
    EstadoDP estado_actual;
    memset(estado_actual.costo, 0, sizeof(estado_actual.costo));

    for (int vecino : adyacencia[nodo]) {
        if (vecino == padre) continue;
        EstadoDP subestado = calcular_dp(vecino, nodo);
        for (int c1 = 1; c1 <= 3; ++c1) {
            for (int c2 = 1; c2 <= 3; ++c2) {
                if (c1 != c2) {
                    estado_actual.costo[c1][c2] += subestado.costo[c1][c2];
                }
            }
        }
    }

    memset(memo[nodo].costo, 0, sizeof(memo[nodo].costo));
    memo[nodo].costo[1][2] = costo_color[1][nodo] + estado_actual.costo[2][3];
    memo[nodo].costo[1][3] = costo_color[1][nodo] + estado_actual.costo[3][2];
    memo[nodo].costo[2][1] = costo_color[2][nodo] + estado_actual.costo[1][3];
    memo[nodo].costo[2][3] = costo_color[2][nodo] + estado_actual.costo[3][1];
    memo[nodo].costo[3][1] = costo_color[3][nodo] + estado_actual.costo[1][2];
    memo[nodo].costo[3][2] = costo_color[3][nodo] + estado_actual.costo[2][1];
    return memo[nodo];
}

void reconstruir_solucion(int nodo, int padre, int color_actual, ll costo_acumulado, int color_anterior) {
    asignacion[nodo] = color_actual;
    for (int vecino : adyacencia[nodo]) {
        if (vecino == padre) continue;
        ll min_costo = 1e18;
        int mejor_color = 0;
        for (int c = 1; c <= 3; ++c) {
            if (color_actual != c && c != color_anterior) {
                if (memo[nodo].costo[color_actual][c] < min_costo) {
                    min_costo = memo[nodo].costo[color_actual][c];
                    mejor_color = c;
                }
            }
        }
        reconstruir_solucion(vecino, nodo, mejor_color, costo_acumulado - costo_color[color_actual][nodo], color_actual);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int c = 1; c <= 3; ++c) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &costo_color[c][i]);
        }
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        adyacencia[u].push_back(v);
        adyacencia[v].push_back(u);
        grado[u]++;
        grado[v]++;
    }
    for (int i = 1; i <= n; ++i) {
        if (grado[i] >= 3) {
            printf("-1\n");
            return 0;
        }
    }
    int raiz = -1;
    for (int i = 1; i <= n; ++i) {
        if (grado[i] == 1) {
            raiz = i;
            break;
        }
    }
    EstadoDP estado_raiz = calcular_dp(raiz, 0);
    ll costo_minimo = 1e18;
    int color_inicial = 0;
    for (int c1 = 1; c1 <= 3; ++c1) {
        for (int c2 = 1; c2 <= 3; ++c2) {
            if (c1 != c2 && estado_raiz.costo[c1][c2] < costo_minimo) {
                costo_minimo = estado_raiz.costo[c1][c2];
                color_inicial = c1;
            }
        }
    }
    reconstruir_solucion(raiz, 0, color_inicial, costo_minimo, -1);
    printf("%lld\n", costo_minimo);
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", asignacion[i], i == n ? '\n' : ' ');
    }
    return 0;
}

Problema E: Minimizar la Diferencia

La solución utiliza un multiset para gestionar los valores extremos de la secuencia. Se reducen iterativamente los valores máximos y mínimos, aujstando las frecuencias y consumiendo operaciones disponibles (k) para minimizar la diferencia final. Este enfoque permite manejar eficientemente las actualizaciones de los extremos.

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

int main() {
    int n;
    ll k;
    scanf("%d%lld", &n, &k);
    multiset<ll> conjunto;
    for (int i = 0; i < n; ++i) {
        ll valor;
        scanf("%lld", &valor);
        conjunto.insert(valor);
    }

    ll min_actual = *conjunto.begin();
    auto iter_max = conjunto.end();
    --iter_max;
    ll max_actual = *iter_max;

    ll conteo_min = conjunto.count(min_actual);
    ll conteo_max = conjunto.count(max_actual);
    conjunto.erase(min_actual);
    conjunto.erase(max_actual);

    while (min_actual < max_actual) {
        if (conjunto.empty()) {
            ll incremento = k / min(conteo_min, conteo_max);
            min_actual = min(max_actual, min_actual + incremento);
            break;
        }

        ll nuevo_min = *conjunto.begin();
        ll nuevo_max = *(--conjunto.end());

        if (conteo_min < conteo_max) {
            ll delta = nuevo_min - min_actual;
            if (k > conteo_min * delta) {
                k -= conteo_min * delta;
                min_actual = nuevo_min;
                conteo_min += conjunto.count(nuevo_min);
                conjunto.erase(nuevo_min);
            } else {
                min_actual = min(max_actual, min_actual + k / conteo_min);
                break;
            }
        } else {
            ll delta = max_actual - nuevo_max;
            if (k > conteo_max * delta) {
                k -= conteo_max * delta;
                max_actual = nuevo_max;
                conteo_max += conjunto.count(nuevo_max);
                conjunto.erase(nuevo_max);
            } else {
                max_actual = max(min_actual, max_actual - k / conteo_max);
                break;
            }
        }
    }

    ll resultado = max_actual - min_actual;
    printf("%lld\n", max(0LL, resultado));
    return 0;
}