Problema A - Twice

Enunciado

Dada una secuencia de longitud \\(n\\), en cada operación se eligen dos índices \\(i, j\\). Si \\(a_i = a_j\\) y ninguno de los índices ha sido seleccionado previamente, la respuesta se incrementa en 1. Se debe determinar el valor máximo posible de la respuesta.

Enfoque

Simulación directa.

Solución

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

bool usados[1000005];

void resolver() {
    int total, conteo = 0;
    cin >> total;
    memset(usados, 0, sizeof(usados));
    vector<int> datos(total);
    for (int idx = 0; idx < total; ++idx)
        cin >> datos[idx];
    
    for (int a = 0; a < total; ++a) {
        for (int b = a + 1; b < total; ++b) {
            if (datos[a] == datos[b] && !usados[a] && !usados[b]) {
                ++conteo;
                usados[a] = usados[b] = true;
            }
        }
    }
    cout << conteo << "\n";
}

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

Problema B - Intercepted Inputs

Enunciado

Se reciben \\(k\\) números enteros. Estos corresponden a la cantidad de elementos de una matriz \\(n \\times m\\) más los dos valores \\(n\\) y \\(m\\) mismos. Se debe encontrar cualquier par \\((n, m)\\) tal que \\(n \\times m + 2 = k\\) y ambos \\(n\\) y \\(m\\) aparezcan en la lista de entrada.

Enfoque

Se recorre la lista de números. Para cada número \\(v[i]\\), se verifica si \\(k-2\\) es divisible por \\(v[i]\\) y si el cociente ya ha sido visto anteriormente. Esto se puede implementar con un conjunto o un mapa de frecuencias.

Solución

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

void resolver() {
    int cantidad;
    cin >> cantidad;
    vector<int> valores(cantidad);
    for (int i = 0; i < cantidad; ++i)
        cin >> valores[i];

    int objetivo = cantidad - 2;
    unordered_set<int> vistos;
    for (int elem : valores) {
        if (elem != 0 && objetivo % elem == 0) {
            int complemento = objetivo / elem;
            if (vistos.count(complemento)) {
                cout << elem << " " << complemento << "\n";
                return;
            }
        }
        vistos.insert(elem);
    }
}

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

Problema C - Superultra's Favorite Permutation

Enunciado

Dado un entero \\(n\\), construir una permutación de los números del 1 al \\(n\\) tal que la suma de cada par de elementos consecutivos sea un número compuesto. Si no existe tal permutación, se debe reportar -1.

Enfoque

Para \\(n \\le 4\\) no existe solución. La idea es separar números pares e impares, ya que la suma de dos pares o dos impares es siempre par y, por lo tanto, compuesta (excepto si es 2, pero eso no ocurre aquí). Luego, se coloca un par específico (como 4 y 5) en la unión para garantizar la condición de número compuesto.

Solución

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

void resolver() {
    int n;
    cin >> n;
    if (n <= 4) {
        cout << -1 << "\n";
        return;
    }
    
    // Imprimir impares excepto 5
    for (int val = 1; val <= n; val += 2)
        if (val != 5) cout << val << " ";
    
    // Imprimir puente 5 y 4
    cout << 5 << " " << 4 << " ";
    
    // Imprimir pares excepto 4
    for (int val = 2; val <= n; val += 2)
        if (val != 4) cout << val << " ";
    
    cout << "\n";
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int consultas;
    cin >> consultas;
    while (consultas--) resolver();
    return 0;
}

Problema D - Sharky Surfing

Enunciado

Existen \\(n\\) obstáculos, cada uno representado por un intervalo \\([l_i, r_i]\\). Para superar el obstáculo \\(i\\) se debe saltar desde \\(l_i - 1\\) hasta \\(r_i + 1\\). Hay \\(m\\) ítems en posiciones \\(x_j\\) que incrementan la capacidad de salto en \\(v_j\\). Comenzendo en la posición 1 con capacidad de salto 1, se quiere llegar a la posición \\(L\\). Se debe calcular el mínimo número de ítems necesarios o determinar que es imposible.

Enfoque

Se itera sobre los obstáculos en orden. Para cada obstáculo, se recogen todos los ítems que aparecen antes de su inicio. Se utiliza una cola de prioridad (o multiset) para almacenar las mejoras disponibles. Se toma repetidamente la mejora más grande hasta que la capacidad de salto supere la longitud del obstáculo actual. Si no es posible, se retorna -1.

Solución

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

void resolver() {
    int n, m, L;
    cin >> n >> m >> L;
    
    vector<pair<int,int>> bloqueos(n);
    for (auto & [l, r] : bloqueos) cin >> l >> r;
    
    vector<pair<int,int>> potenciadores(m);
    for (auto & [pos, val] : potenciadores) cin >> pos >> val;
    
    priority_queue<int> disponibles;
    int poder = 1, necesarios = 0, idxItem = 0;
    
    for (auto & [ini, fin] : bloqueos) {
        // Recolectar potenciadores antes del obstáculo
        while (idxItem < m && potenciadores[idxItem].first < ini) {
            disponibles.push(potenciadores[idxItem].second);
            ++idxItem;
        }
        
        // Necesitamos poder >= (fin - ini + 1) para saltar
        int requerido = fin - ini + 1;
        while (!disponibles.empty() && poder <= requerido) {
            poder += disponibles.top();
            disponibles.pop();
            ++necesarios;
        }
        
        if (poder <= requerido) {
            cout << -1 << "\n";
            return;
        }
    }
    
    cout << necesarios << "\n";
}

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