Optimización de Distancia en Ascensores

Para determinar el piso óptimo donde ubicar un ascensor y minimizar la distancia total de recorrido, se evalúa el costo de establecer el ascensor en cada uno de los pisos disponibles. El costo se calcula sumando las distancias de ida y vuelta para cada persona, considerando su piso de origen, el piso del ascensor y la planta baja. Se implementa una búsqueda exhaustiva sobre todas las posibles ubicaciones para encontrar el mínimo global.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int total_floors;
    if (!(cin >> total_floors)) return 0;

    vector<long long> residents(total_floors + 1);
    for (int i = 1; i <= total_floors; ++i) {
        cin >> residents[i];
    }

    long long minimum_cost = 1e18;
    for (int base_floor = 1; base_floor <= total_floors; ++base_floor) {
        long long current_cost = 0;
        for (int target_floor = 1; target_floor <= total_floors; ++target_floor) {
            long long travel_distance = abs(base_floor - target_floor) + abs(target_floor - 1) + abs(base_floor - 1);
            current_cost += travel_distance * 2LL * residents[target_floor];
        }
        minimum_cost = min(minimum_cost, current_cost);
    }

    cout << minimum_cost << "\n";
    return 0;
}

Distribución Óptima de Volumen en Contenedores

El objetivo es extraer un volumen específico de líquido de un conjunto de barriles de manera que se maximice la cantidad mínima restante en cualquier barril. Primero, se verifica si la capacidad total es suficiente para satisfacer la demanda. Si es viable, se calcula la distribución óptima restando el exceso de capacidad y ajustando el valor mínimo garantizado mediante operaciones aritméticas directas.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_barrels;
    long long required_volume;
    cin >> num_barrels >> required_volume;

    vector<long long> capacities(num_barrels);
    long long total_capacity = 0;
    long long min_capacity = 2e9;

    for (int i = 0; i < num_barrels; ++i) {
        cin >> capacities[i];
        total_capacity += capacities[i];
        min_capacity = min(min_capacity, capacities[i]);
    }

    if (total_capacity < required_volume) {
        cout << -1 << "\n";
    } else {
        long long excess_to_distribute = required_volume - (total_capacity - min_capacity * num_barrels);
        if (excess_to_distribute > 0) {
            min_capacity -= (excess_to_distribute - 1) / num_barrels + 1;
        }
        cout << min_capacity << "\n";
    }

    return 0;
}

Conteo de Subsecuencias con Separadores

Para contar subsecuencias válidas de caracteres 'a' separadas por 'b', se emplea un enfoque combinatorio iterativo. Cada segmento continuo de 'a' ofrece múltiples opciones de selección. Al encontrar un separador 'b', el número de estados acumulados se multiplica por las opciones del segmento anterior más uno, representando la alternativa de no seleccionar ningún carácter de dicho segmento. Las operaciones se realizan bajo aritmética modular.

#include <iostream>
#include <string>

using namespace std;

const long long MODULO = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string sequence;
    cin >> sequence;

    char previous_char = 'b';
    long long consecutive_count = 1;
    long long valid_subsequences = 0;
    long long state_multiplier = 1;

    for (char current_char : sequence) {
        if (current_char == 'a') {
            if (previous_char == 'a') {
                consecutive_count++;
            } else {
                previous_char = 'a';
                consecutive_count = 1;
            }
            valid_subsequences = (valid_subsequences + state_multiplier) % MODULO;
        } else if (current_char == 'b') {
            if (previous_char == 'a') {
                state_multiplier = (state_multiplier * (consecutive_count + 1)) % MODULO;
                previous_char = 'b';
                consecutive_count = 1;
            }
        }
    }

    cout << valid_subsequences << "\n";
    return 0;
}

Camino de Máximo Peso en Estructuras Arbóreas

En un árbol con pesos asignados a los nodos y costos en las aristas, se busca identificar el camino que maximice la suma de pesos. Mediante un recorrido en profundidad (DFS), se calculan las dos mejores contribuciones de los subárboles hijos para cada nodo procesado. La respuesta global se actualiza combinando estas dos mejores rutas, restando el peso del nodo raíz actual para evitar duplicaciones en la suma total.

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

using namespace std;

struct Edge {
    int destination;
    long long cost;
};

int node_count;
vector<long long> node_weights;
vector<vector<Edge>> tree_adjacency;
long long global_max_path = 0;

long long traverse_tree(int current_node, int parent_node) {
    long long primary_max = node_weights[current_node];
    long long secondary_max = node_weights[current_node];

    for (const auto& edge : tree_adjacency[current_node]) {
        if (edge.destination == parent_node) continue;

        long long child_contribution = traverse_tree(edge.destination, current_node) + node_weights[current_node] - edge.cost;

        if (child_contribution > primary_max) {
            secondary_max = primary_max;
            primary_max = child_contribution;
        } else if (child_contribution > secondary_max) {
            secondary_max = child_contribution;
        }
    }

    global_max_path = max(global_max_path, primary_max + secondary_max - node_weights[current_node]);
    return primary_max;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> node_count;
    node_weights.resize(node_count + 1);
    tree_adjacency.resize(node_count + 1);

    for (int i = 1; i <= node_count; ++i) {
        cin >> node_weights[i];
    }

    for (int i = 0; i < node_count - 1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        tree_adjacency[u].push_back({v, w});
        tree_adjacency[v].push_back({u, w});
    }

    traverse_tree(1, 0);
    cout << global_max_path << "\n";

    return 0;
}

Conteo de Nodos en Árboles de Prefijos Acotados

Este problema requiere contar los nodos en un árbol binario de prefijos delimitado por dos cadenas de caracteres, limitando el conteo en cada nivel a un valor máximo predefinido. Se itera a través de la profundidad del árbol, manteniendo un registro de los nodos que se ramifican fuera de los límites estrictos de las cadenas. Cuando el árbol se ramfiica, el número de nodos válidos crece exponencialmente, aplicando el límite superior en cada paso para evitar desbordamientos y garantizar la eficiencia.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int string_length;
    long long max_nodes_per_level;
    cin >> string_length >> max_nodes_per_level;

    string lower_limit, upper_limit;
    cin >> lower_limit >> upper_limit;

    long long total_valid_nodes = 0;
    long long diverged_nodes = 0;
    bool has_diverged = false;

    for (int i = 0; i < string_length; ++i) {
        long long boundary_contribution = 0;
        if (lower_limit[i] == 'a') {
            boundary_contribution = (upper_limit[i] == 'b') ? 2 : 1;
        } else {
            boundary_contribution = (upper_limit[i] == 'a') ? 0 : 1;
        }

        if (!has_diverged) {
            if (boundary_contribution == 2) has_diverged = true;
            total_valid_nodes += min(boundary_contribution, max_nodes_per_level);
            continue;
        }

        diverged_nodes = min(max_nodes_per_level, diverged_nodes * 2 + boundary_contribution);
        total_valid_nodes += min(max_nodes_per_level, diverged_nodes + 2);
    }

    cout << total_valid_nodes << "\n";
    return 0;
}