Este artículo aborda las soluciones de los problemas del Grupo C del concurso mensual de marzo. Los conceptos aplicados incluyen matemáticas, pensamiento lógico, algoritmos voraces y estructuras de datos como mapas.

Problema 1: Entero más cercano múltiplo

Etiquetas: Matemáticas
Enunciado: Dados dos enteros positivos n y d, hallar todos los enteros más cercanos a n que sean múltiplos de d. Si existen varios, ordenarlos de manera ascendente. Restrciciones: 1 ≤ n, d ≤ 1,000,000,000.
Solución: Se calcula el múltiplo inferior mediante (n / d) * d y el superior con (n / d + 1) * d. Luego, se comparan las distancias absolutas a n para determinar cuál o cuáles son los más cercanos.
Código:

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    ll valor_n, valor_d;
    cin >> valor_n >> valor_d;
    ll candidato_inferior = (valor_n / valor_d) * valor_d;
    ll candidato_superior = (valor_n / valor_d + 1) * valor_d;
    ll dist_inf = abs(candidato_inferior - valor_n);
    ll dist_sup = abs(candidato_superior - valor_n);
    if (dist_inf < dist_sup)
        cout << candidato_inferior;
    else if (dist_inf > dist_sup)
        cout << candidato_superior;
    else
        cout << candidato_inferior << "\n" << candidato_superior;
    return 0;
}

Problema 2: Verificación de progresión aritmética

Etiquetas: Secuencias aritméticas, Matemáticas
Enunciado: Dado un entero n y una secuencia a1, a2, ..., an, determinar si la secuencia forma una progresión aritmética.
Solución: Se obtiene la diferencia común a partir de los dos primeros términos. A continuación, se verifica si la diferencia entre cada par consecutivo de términos coincide con dicha diferencia común.
Código:

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int cantidad;
    cin >> cantidad;
    vector<ll> secuencia(cantidad);
    for (int idx = 0; idx < cantidad; ++idx)
        cin >> secuencia[idx];
    if (cantidad < 2) {
        cout << "Secuencia Aritmética";
        return 0;
    }
    ll diferencia_comun = secuencia[1] - secuencia[0];
    for (int idx = 2; idx < cantidad; ++idx) {
        if (secuencia[idx] - secuencia[idx - 1] != diferencia_comun) {
            cout << "No";
            return 0;
        }
    }
    cout << "Secuencia Aritmética";
    return 0;
}

Problema 3: Viaje con trabajo temporal

Etiquetas: Algoritmos voraces
Enunciado: Se tiene un segmento de posiciones de 1 a n. Al pasar por la posición i, se incurre en un costo ci. Trabajar un día en la posición i genera una ganancia ai. Se puede trabajar múltiples días en una misma posición. Hallar el mínimo número de días de trabajo requeridos para viajar de la posición 1 a la n.
Solución: Se utiliza un enfoque voraz. Se mantiene un registro de la ganancia máxima por día disponible hasta la posición actual. Si el dinero acumulado es insuficiente para cubrir el costo de la posición, se calculan los días necesarios trabajando en el punto con mayor rendimiento, actualizando el total de días y el saldo restante.
Código:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    int num_posiciones;
    cin >> num_posiciones;
    vector<ll> ganancia(num_posiciones), costo(num_posiciones);
    for (int i = 0; i < num_posiciones; ++i)
        cin >> ganancia[i] >> costo[i];
    ll max_ganancia_diaria = 0, dias_totales = 0, dinero_actual = 0;
    for (int i = 0; i < num_posiciones; ++i) {
        max_ganancia_diaria = max(max_ganancia_diaria, ganancia[i]);
        if (dinero_actual < costo[i]) {
            ll faltante = costo[i] - dinero_actual;
            ll dias_necesarios = (faltante + max_ganancia_diaria - 1) / max_ganancia_diaria;
            dias_totales += dias_necesarios;
            dinero_actual += dias_necesarios * max_ganancia_diaria - costo[i];
        } else {
            dinero_actual -= costo[i];
        }
    }
    cout << dias_totales;
    return 0;
}

Problema 4: Registro consolidado de transacciones

Etiquetas: Mapas, Estructuras de datos
Enunciado: Dado n operaciones de compra o venta de acciones, cada una con un precio unitario ai y una cantidad bi, fusionar las transacciones por precio. Las compras se ordenan por precio ascendente y las ventas por precio descendente.
Solución: Se emplean dos mapas: uno para compras (ordenado ascendente por clave) y otro para ventas (ordenado descendente por clave). Al procesar cada operación, se acumulan las cantidades en el mapa correspondiente. Finalmente, se imprimen los registros agrupados.
Código:

#include <iostream>
#include <map>
#include <string>
using namespace std;
using ll = long long;

int main() {
    int num_operaciones;
    cin >> num_operaciones;
    map<ll, ll, less<ll>> compras;
    map<ll, ll, greater<ll>> ventas;
    string tipo;
    ll precio, cantidad;
    for (int i = 0; i < num_operaciones; ++i) {
        cin >> tipo >> precio >> cantidad;
        if (tipo == "COMPRA")
            compras[precio] += cantidad;
        else if (tipo == "VENTA")
            ventas[precio] += cantidad;
    }
    cout << compras.size() + ventas.size() << "\n";
    for (const auto& par : compras)
        cout << "COMPRA " << par.first << " " << par.second << "\n";
    for (const auto& par : ventas)
        cout << "VENTA " << par.first << " " << par.second << "\n";
    return 0;
}

Problema 5: Optimización de velocidad con límites

Etiquetas: Matemáticas, Pensamiento lógico
Enunciado: Un vehículo comienza en la coordenada 0 con velocidad inicial 1. Por cada unidad de distancia avanzada, la velocidad puede mantenerse, aumentar en 1 o disminuir en 1, sin bajar de 1. Existen n puntos de límite en coordenadas xi con velocidad máxima Li. Tras pasar el último punto, finaliza el recorrido. Determinar la velocidad máxima alcanzable durante el viaje.
Solución: Se realiza un preprocesamiento de atrás hacia adelante para ajustar los límites de velocidad considerando la distancia entre puntos. Luego, se avanza hacia adelante calculando la velocidad máxima factible en cada punto, y se determina el pico máximo usando una fórmula basada en las velocidades consecutivas y la distancia.
Código:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    int num_puntos;
    cin >> num_puntos;
    vector<ll> coordenada(num_puntos + 1), limite(num_puntos + 1);
    coordenada[0] = 0;
    for (int i = 1; i <= num_puntos; ++i)
        cin >> coordenada[i] >> limite[i];
    for (int i = num_puntos; i >= 2; --i) {
        ll dist = coordenada[i] - coordenada[i - 1];
        if (limite[i] < limite[i - 1])
            limite[i - 1] = min(limite[i - 1], limite[i] + dist);
    }
    vector<ll> velocidad_max(num_puntos + 1);
    velocidad_max[0] = 1;
    ll max_velocidad_global = 1;
    for (int i = 1; i <= num_puntos; ++i) {
        ll dist = coordenada[i] - coordenada[i - 1];
        velocidad_max[i] = min(velocidad_max[i - 1] + dist, limite[i]);
        ll velocidad_media = (velocidad_max[i] + velocidad_max[i - 1] + dist) / 2;
        max_velocidad_global = max(max_velocidad_global, velocidad_media);
    }
    cout << max_velocidad_global;
    return 0;
}