Codeforces Round 920 División 3

Problema A - Cuadrado

Dado cuatro puntos que definen un cuadrado, calcular su área basándose en las coordenadas únicas de los ejes.

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

void resolverCaso() {
    vector<int> ejeX, ejeY;
    for (int idx = 0; idx < 4; ++idx) {
        int puntoX, puntoY;
        cin >> puntoX >> puntoY;
        ejeX.push_back(puntoX);
        ejeY.push_back(puntoY);
    }
    sort(ejeX.begin(), ejeX.end());
    sort(ejeY.begin(), ejeY.end());
    int base = ejeX[1] - ejeX[0];
    int altura = ejeY[1] - ejeY[0];
    cout << abs(base * altura) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int totalCasos;
    cin >> totalCasos;
    while (totalCasos--) resolverCaso();
    return 0;
}

Problema B - Orgenizando Gatos

Comparar dos secuencias de gatos representadas por cadenas y determinar el número mínimo de operaciones para hacerlas iguales.

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

void calcularDiferencias() {
    int longitud;
    string secuenciaObjetivo, secuenciaActual;
    cin >> longitud;
    cin >> secuenciaObjetivo >> secuenciaActual;
    int conteo1 = 0, conteo2 = 0;
    for (int pos = 0; pos < longitud; ++pos) {
        if (secuenciaObjetivo[pos] == '1' && secuenciaActual[pos] == '0') conteo1++;
        else if (secuenciaObjetivo[pos] == '0' && secuenciaActual[pos] == '1') conteo2++;
    }
    cout << max(conteo1, conteo2) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int pruebas;
    cin >> pruebas;
    while (pruebas--) calcularDiferencias();
    return 0;
}

Problema C - Enviando Mensajes

Evaluar si es posible enviar todos los mensajes con un presupuesto dado, considerando costos por unidad de distancia y costos fijos.

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

void verificarEnvio() {
    int numMensajes, costoInicial, costoPorUnidad, costoFijo;
    cin >> numMensajes >> costoInicial >> costoPorUnidad >> costoFijo;
    vector<int> posiciones(numMensajes + 1);
    posiciones[0] = 0;
    for (int i = 1; i <= numMensajes; ++i) cin >> posiciones[i];
    int saldo = costoInicial;
    for (int i = 1; i <= numMensajes; ++i) {
        int distancia = posiciones[i] - posiciones[i-1];
        int costo = min(distancia * costoPorUnidad, costoFijo);
        saldo -= costo;
        if (saldo <= 0) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "SÍ" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int casos;
    cin >> casos;
    while (casos--) verificarEnvio();
    return 0;
}

Problema D - Arreglo Muy Diferente

Maximizar la diferencia absoluta total entre elementos de dos arrreglos mediante asignación óptima.

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

long long maximizarDiferencia() {
    int tamanoA, tamanoB;
    cin >> tamanoA >> tamanoB;
    deque<int> arregloA(tamanoA);
    for (int i = 0; i < tamanoA; ++i) cin >> arregloA[i];
    vector<int> arregloB(tamanoB);
    for (int i = 0; i < tamanoB; ++i) cin >> arregloB[i];
    sort(arregloB.begin(), arregloB.end());
    sort(arregloA.begin(), arregloA.end());
    int izquierda = 0, derecha = tamanoB - 1;
    long long sumaTotal = 0;
    while (!arregloA.empty()) {
        int valorFrontal = arregloA.front();
        int valorTrasero = arregloA.back();
        int opcion1 = abs(valorFrontal - arregloB[izquierda]);
        int opcion2 = abs(valorFrontal - arregloB[derecha]);
        int opcion3 = abs(valorTrasero - arregloB[izquierda]);
        int opcion4 = abs(valorTrasero - arregloB[derecha]);
        int maxOpcion = max({opcion1, opcion2, opcion3, opcion4});
        if (maxOpcion == opcion1 || maxOpcion == opcion2) {
            sumaTotal += maxOpcion;
            if (maxOpcion == opcion1) izquierda++;
            else derecha--;
            arregloA.pop_front();
        } else {
            sumaTotal += maxOpcion;
            if (maxOpcion == opcion3) izquierda++;
            else derecha--;
            arregloA.pop_back();
        }
    }
    return sumaTotal;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int pruebas;
    cin >> pruebas;
    while (pruebas--) cout << maximizarDiferencia() << endl;
    return 0;
}

Problema E - Comer la Ficha

Determinar el resultado de un juego en una cuadrícula donde dos jugadores se mueven hacia arriba y abajo respectivamente.

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

string resolverJuego() {
    int alto, ancho, fila1, col1, fila2, col2;
    cin >> alto >> ancho >> fila1 >> col1 >> fila2 >> col2;
    if (fila1 >= fila2) return "Empate";
    int diferenciaFilas = fila2 - fila1 - 1;
    int pasos = diferenciaFilas / 2;
    if (diferenciaFilas % 2 == 1) {
        int limiteIzq1 = max(1, col1 - pasos - 1);
        int limiteDer1 = min(ancho, col1 + pasos + 1);
        int limiteIzq2 = max(1, col2 - pasos);
        int limiteDer2 = min(ancho, col2 + pasos);
        if (limiteIzq2 <= limiteIzq1 && limiteDer2 >= limiteDer1) return "Bob";
        else return "Empate";
    } else {
        int limiteIzq1 = max(1, col2 - pasos);
        int limiteDer1 = min(ancho, col2 + pasos);
        int limiteIzq2 = max(1, col1 - pasos - 1);
        int limiteDer2 = min(ancho, col1 + pasos + 1);
        if (limiteIzq2 <= limiteIzq1 && limiteDer2 >= limiteDer1) return "Alice";
        else return "Empate";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int casos;
    cin >> casos;
    while (casos--) cout << resolverJuego() << endl;
    return 0;
}

Porblema F - Suma de Progresión

Calcular sumas de progresiones aritméticas en un arreglo, con precomputación para pasos pequeños.

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

const int MAX_PASO = 200;
const int MAX_N = 100000;

void resolverConsultas() {
    int n, q;
    cin >> n >> q;
    vector<int> arreglo(n + 1);
    for (int i = 1; i <= n; ++i) cin >> arreglo[i];
    vector<vector<long long>> precalculo(n + 1, vector<long long>(MAX_PASO + 1, 0));
    vector<vector<long long>> sumaAcum(n + 1, vector<long long>(MAX_PASO + 1, 0));
    for (int paso = 1; paso <= MAX_PASO; ++paso) {
        for (int indice = 1; indice <= n; ++indice) {
            if (indice - paso <= 0) {
                precalculo[indice][paso] = arreglo[indice];
                sumaAcum[indice][paso] = arreglo[indice];
            } else {
                int factor = (indice - 1) / paso + 1;
                precalculo[indice][paso] = precalculo[indice - paso][paso] + arreglo[indice] * factor;
                sumaAcum[indice][paso] = sumaAcum[indice - paso][paso] + arreglo[indice];
            }
        }
    }
    while (q--) {
        int inicio, paso, longitud;
        cin >> inicio >> paso >> longitud;
        long long resultado = 0;
        if (paso > MAX_PASO) {
            for (int i = 0; i < longitud; ++i) resultado += arreglo[inicio + i * paso] * (i + 1);
        } else {
            int final = inicio + (longitud - 1) * paso;
            if (inicio - paso <= 0) {
                resultado = precalculo[final][paso];
            } else {
                resultado = precalculo[final][paso] - precalculo[inicio - paso][paso];
                int factorBase = (inicio - 1) / paso;
                resultado -= (sumaAcum[final][paso] - sumaAcum[inicio - paso][paso]) * factorBase;
            }
        }
        cout << resultado << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int pruebas;
    cin >> pruebas;
    while (pruebas--) resolverConsultas();
    return 0;
}