A. Contenido Demasiado Grande

Este problema requiere verificar si la suma de todos los elementos en un arreglo es menor o igual que un valor dado M. Es una tarea directa que no requiere implementación compleja.

B. Concatenación de Cadenas

Dado un conjunto de n cadenas de caracteres, se generan n(n-1) concatenaciones al combinar pares distintos. El objetivo es contar cuántas de estas concatenaciones son únicas. Para n limitado a 100, se puede usar una estructura de conjunto para eliminar duplicados de manera eficiente.

C. Cola Grande

Se simula una cola con operaciones de inserción masiva y extracción con suma. En lugar de procesar cada elemento individualmente, se mantiene un registro de posiciones finales para cada inserción. Al extraer elementos, se utiliza búsqueda binaria para identificar los intervalos relevantes y se calcula la suma acumulada. Esto reduce la complejidad temporal a O(n log n) ya que cada inserción se consulta como máximo una vez.

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

int main() {
    int operaciones;
    cin >> operaciones;
    vector<ll> finales(1, 0), valores;
    ll posicion_frente = 1, total_ins = 0;
    while (operaciones--) {
        int tipo;
        cin >> tipo;
        if (tipo == 1) {
            ll cantidad, valor;
            cin >> cantidad >> valor;
            total_ins++;
            valores.push_back(valor);
            finales.push_back(finales.back() + cantidad);
        } else {
            ll k;
            cin >> k;
            ll izq = lower_bound(finales.begin(), finales.end(), posicion_frente) - finales.begin();
            ll der = lower_bound(finales.begin(), finales.end(), posicion_frente + k - 1) - finales.begin();
            ll resultado = (finales[izq] - posicion_frente + 1) * valores[izq - 1];
            for (ll i = izq; i < der; i++) {
                resultado += (finales[i + 1] - finales[i]) * valores[i];
            }
            resultado -= (finales[der] - (posicion_frente + k - 1)) * valores[der - 1];
            cout << resultado << '\n';
            posicion_frente += k;
        }
    }
    return 0;
}

D. Secuencia Geométrica

Para determinar si una secuencia numérica es una reordenación de una progresión geométrica, se ordenan los elementos por valor absoluto. Si la razón no es -1, se verifica la condición a_{i-1} * a_{i+1} = a_i^2 para todos los i internos. Se añaden casos especiales para razones negativas y ceros.

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

bool comparar_absoluto(ll a, ll b) {
    return abs(a) < abs(b);
}

void resolver() {
    int n;
    cin >> n;
    vector<ll> secuencia(n);
    for (int i = 0; i < n; i++) cin >> secuencia[i];
    sort(secuencia.begin(), secuencia.end(), comparar_absoluto);
    if (abs(secuencia[0]) == abs(secuencia[n - 1])) {
        int positivos = 0;
        for (ll num : secuencia) if (num > 0) positivos++;
        if (positivos == n || positivos == 0) cout << "Yes\n";
        else if (n % 2 == 0 && positivos == n / 2) cout << "Yes\n";
        else if (n % 2 == 1 && (positivos == n / 2 || positivos == n - n / 2)) cout << "Yes\n";
        else cout << "No\n";
        return;
    }
    for (int i = 1; i < n - 1; i++) {
        if (secuencia[i - 1] * secuencia[i + 1] != secuencia[i] * secuencia[i]) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main() {
    int pruebas;
    cin >> pruebas;
    while (pruebas--) resolver();
    return 0;
}

E. Reversión 2^i

Dada una permutación de longitud 2^n, se pueden invertir segmentos de tamaño potencia de dos. Para minimizar el orden lexicográfico, se aplica un enfoque recursivo: para cada intervalo, se coloca el valor mínimo en la primera posición invirtiendo si es necesario, y luego se divide el problema. La complejidad total es O(n 2^n).

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

void ordenar_minimo(vector<int>& arreglo, int inicio, int fin) {
    if (inicio == fin) return;
    int posicion = inicio, medio = (inicio + fin) / 2;
    for (int i = inicio + 1; i <= fin; i++) if (arreglo[i] < arreglo[posicion]) posicion = i;
    if (posicion > medio) {
        for (int i = inicio; i <= medio; i++) swap(arreglo[i], arreglo[fin - (i - inicio)]);
    }
    ordenar_minimo(arreglo, inicio, medio);
    ordenar_minimo(arreglo, medio + 1, fin);
}

int main() {
    int pruebas;
    cin >> pruebas;
    while (pruebas--) {
        int n;
        cin >> n;
        int tam = 1 << n;
        vector<int> permutacion(tam);
        for (int i = 0; i < tam; i++) cin >> permutacion[i];
        ordenar_minimo(permutacion, 0, tam - 1);
        for (int val : permutacion) cout << val << " ";
        cout << '\n';
    }
    return 0;
}

F. Sin Paso

En un juego de cuadrícula, donde un jugador bloquea direcciones y otro se mueve hacia objetivos, se calcula el número mínimo de pasos para cada celda alcanzable. Se usa una actualización similar a BFS: una celda es alcanzable si al menos dos vecinos lo son, y su paso es el segundo mayor valor entre los vecinos más uno. Se propagan las actualizaciones hasta la convergencia.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
using ll = long long;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int main() {
    int filas, columnas, objetivos;
    cin >> filas >> columnas >> objetivos;
    vector<vector<ll>> pasos(filas + 1, vector<ll>(columnas + 1, -1));
    queue<pair<int, int>> cola;
    for (int i = 0; i < objetivos; i++) {
        int x, y;
        cin >> x >> y;
        pasos[x][y] = 0;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && ny >= 1 && nx <= filas && ny <= columnas) {
                cola.push({nx, ny});
            }
        }
    }
    while (!cola.empty()) {
        auto [x, y] = cola.front();
        cola.pop();
        int contador = 0;
        ll min1 = INT_MAX, min2 = INT_MAX;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && ny >= 1 && nx <= filas && ny <= columnas && pasos[nx][ny] != -1) {
                contador++;
                if (pasos[nx][ny] < min1) {
                    min2 = min1;
                    min1 = pasos[nx][ny];
                } else if (pasos[nx][ny] < min2) {
                    min2 = pasos[nx][ny];
                }
            }
        }
        if (contador <= 1 || (pasos[x][y] != -1 && min2 + 1 >= pasos[x][y])) continue;
        pasos[x][y] = min2 + 1;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && ny >= 1 && nx <= filas && ny <= columnas) {
                if (pasos[nx][ny] == -1 || pasos[nx][ny] > min2 + 2) {
                    cola.push({nx, ny});
                }
            }
        }
    }
    ll suma_total = 0;
    for (int i = 1; i <= filas; i++) {
        for (int j = 1; j <= columnas; j++) {
            if (pasos[i][j] != -1) suma_total += pasos[i][j];
        }
    }
    cout << suma_total << endl;
    return 0;
}

G. Cuadrícula Grande Prohibida

Para verificar la conectividad en una cuadrícula con obstáculos, se aplica el concepto de grafos duales. Los obstáculos se conectna en ocho direcciones usando union-find, y se verifica si las fronteras superior-inferior o izquierda-derecha están conectadas, lo que bloquearía el camino entre (1,1) y (n,m).

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

const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1};

int encontrar(int x, vector<int>& padre) {
    if (padre[x] == x) return x;
    return padre[x] = encontrar(padre[x], padre);
}

void unir(int a, int b, vector<int>& padre) {
    a = encontrar(a, padre);
    b = encontrar(b, padre);
    if (a != b) padre[a] = b;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    map<pair<int, int>, int> indice;
    vector<int> padre(k + 5);
    for (int i = 0; i < k + 5; i++) padre[i] = i;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        indice[{x, y}] = i;
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
                if (indice.count({nx, ny})) unir(i, indice[{nx, ny}], padre);
            }
        }
        if (x == 1) unir(i, k + 1, padre);
        if (y == 1) unir(i, k + 2, padre);
        if (x == n) unir(i, k + 3, padre);
        if (y == m) unir(i, k + 4, padre);
    }
    int f1 = encontrar(k + 1, padre), f2 = encontrar(k + 2, padre);
    int f3 = encontrar(k + 3, padre), f4 = encontrar(k + 4, padre);
    if (f1 == f2 || f1 == f3 || f2 == f4 || f3 == f4) cout << "No\n";
    else cout << "Yes\n";
    return 0;
}