A. ¿Está Calificado?
Problema de condiciones simples. Dado un valor de clasificación y una categoría, se determina si cumple con los rengos especificados.
#include <iostream>
using namespace std;
int main() {
int clasificacion, tipo;
cin >> clasificacion >> tipo;
bool valido = false;
if (tipo == 1) {
if (clasificacion >= 1600 && clasificacion <= 2999) {
valido = true;
}
} else {
if (clasificacion >= 1200 && clasificacion <= 2399) {
valido = true;
}
}
cout << (valido ? "Sí" : "No") << endl;
return 0;
}
B. No Todos
Dado un arreglo de longitud N y un valor M, se busca el primer prefijo que contenga todos los valores de 1 a M. La respuesta es la longitud restante del arreglo.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> contador(m + 1, 0);
int distintos = 0;
for (int i = 0; i < n; ++i) {
int valor;
cin >> valor;
if (valor <= m && contador[valor] == 0) {
distintos++;
}
if (valor <= m) {
contador[valor]++;
}
if (distintos == m) {
cout << n - i - 1 << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}
C. Suma de Productos
La suma de productos pares de un arreglo se calcula mediante la fórmula: (∑A_i)² - ∑A_i², dividida por 2.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
ll suma_total = 0, suma_cuadrados = 0;
for (int i = 0; i < n; ++i) {
ll elemento;
cin >> elemento;
suma_total += elemento;
suma_cuadrados += elemento * elemento;
}
ll resultado = (suma_total * suma_total - suma_cuadrados) / 2;
cout << resultado << endl;
return 0;
}
D. Ruta de Escape
En una cuadrícula, se realiza una búsqueda en amplitud desde las salidas para encontrar la ruta más corta a cada celda, asignando direcciones.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const char direcciones[] = {'^', 'v', '<', '>'};
char mapa[1005][1005];
char solucion[1005][1005];
int distancias[1005][1005];
struct Posicion {
int x, y;
};
int main() {
int filas, columnas;
cin >> filas >> columnas;
memset(distancias, 0x3f, sizeof(distancias));
queue<Posicion> cola;
for (int i = 1; i <= filas; ++i) {
for (int j = 1; j <= columnas; ++j) {
cin >> mapa[i][j];
solucion[i][j] = mapa[i][j];
if (mapa[i][j] == 'E') {
cola.push({i, j});
distancias[i][j] = 0;
}
}
}
while (!cola.empty()) {
Posicion actual = cola.front();
cola.pop();
for (int d = 0; d < 4; ++d) {
int nx = actual.x + dx[d];
int ny = actual.y + dy[d];
if (nx >= 1 && ny >= 1 && nx <= filas && ny <= columnas && mapa[nx][ny] == '.') {
if (distancias[nx][ny] > distancias[actual.x][actual.y] + 1) {
distancias[nx][ny] = distancias[actual.x][actual.y] + 1;
solucion[nx][ny] = direcciones[d];
cola.push({nx, ny});
}
}
}
}
for (int i = 1; i <= filas; ++i) {
for (int j = 1; j <= columnas; ++j) {
cout << solucion[i][j];
}
cout << endl;
}
return 0;
}
E. Alineación de Frutas
Problema combinatorio con restricciones de orden. Se calcula el número de permutaciones válidas usando combinatoria y sumas sobre posiciones.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll potencia_modular(ll base, ll exponente) {
ll resultado = 1;
while (exponente > 0) {
if (exponente & 1) {
resultado = resultado * base % MOD;
}
base = base * base % MOD;
exponente >>= 1;
}
return resultado;
}
int main() {
int A, B, C, D;
cin >> A >> B >> C >> D;
int n_max = A + B + C + D;
vector<ll> factorial(n_max + 1, 1);
vector<ll> inverso(n_max + 1, 1);
for (int i = 1; i <= n_max; ++i) {
factorial[i] = factorial[i - 1] * i % MOD;
if (i > 1) {
inverso[i] = MOD - MOD / i * inverso[MOD % i] % MOD;
}
}
vector<ll> inv_factorial(n_max + 1, 1);
for (int i = 2; i <= n_max; ++i) {
inv_factorial[i] = inv_factorial[i - 1] * inverso[i] % MOD;
}
auto combinatoria = [&](int n, int m) -> ll {
if (n < m || m < 0) return 0;
return factorial[n] * inv_factorial[m] % MOD * inv_factorial[n - m] % MOD;
};
ll total = 0;
for (int i = 0; i <= C; ++i) {
ll termino1 = combinatoria(D + C - i - 1, D - 1);
ll termino2 = combinatoria(A + i + B, B);
total = (total + termino1 * termino2 % MOD) % MOD;
}
cout << total << endl;
return 0;
}
F. Cruce de Acordes
Tras transformar índices, se convierte en un problema de contar elementos con frecuencia impar en intervalos. Se aplica el algoritmo de Mo con discretización.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int TAM_BLOQUE = 1000;
struct Consulta {
int izquierda, derecha, id;
bool operator<(const Consulta& otra) const {
if (izquierda / TAM_BLOQUE != otra.izquierda / TAM_BLOQUE) {
return izquierda < otra.izquierda;
}
if ((izquierda / TAM_BLOQUE) % 2 == 1) {
return derecha < otra.derecha;
}
return derecha > otra.derecha;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> segmentos(m);
vector<int> puntos_compresion;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
a /= 2;
b /= 2;
segmentos[i] = {a, b};
puntos_compresion.push_back(a);
puntos_compresion.push_back(b);
}
sort(puntos_compresion.begin(), puntos_compresion.end());
puntos_compresion.erase(unique(puntos_compresion.begin(), puntos_compresion.end()), puntos_compresion.end());
int tam_compress = puntos_compresion.size();
vector<int> asignacion(m * 2);
for (int i = 0; i < m; ++i) {
auto [a, b] = segmentos[i];
int idx_a = lower_bound(puntos_compresion.begin(), puntos_compresion.end(), a) - puntos_compresion.begin();
int idx_b = lower_bound(puntos_compresion.begin(), puntos_compresion.end(), b) - puntos_compresion.begin();
asignacion[idx_a] = i + 1;
asignacion[idx_b] = i + 1;
}
vector<int> bloque_indice(tam_compress + 1);
for (int i = 0; i < tam_compress; ++i) {
bloque_indice[i] = i / TAM_BLOQUE;
}
int q;
cin >> q;
vector<Consulta> consultas(q);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
if (l > r) swap(l, r);
l = (l + 1) / 2;
r = (r - 1) / 2;
l = lower_bound(puntos_compresion.begin(), puntos_compresion.end(), l) - puntos_compresion.begin();
r = upper_bound(puntos_compresion.begin(), puntos_compresion.end(), r) - puntos_compresion.begin() - 1;
consultas[i] = {l, r, i};
}
sort(consultas.begin(), consultas.end());
vector<int> frecuencia(tam_compress + 1, 0);
vector<int> conteo_frecuencia(m + 1, 0);
int respuesta_actual = 0;
auto agregar = [&](int posicion) {
int valor = asignacion[posicion];
if (valor == 0) return;
if (conteo_frecuencia[valor] == 1) {
respuesta_actual--;
} else if (conteo_frecuencia[valor] == 0) {
respuesta_actual++;
}
conteo_frecuencia[valor]++;
};
auto remover = [&](int posicion) {
int valor = asignacion[posicion];
if (valor == 0) return;
if (conteo_frecuencia[valor] == 1) {
respuesta_actual--;
} else if (conteo_frecuencia[valor] == 2) {
respuesta_actual++;
}
conteo_frecuencia[valor]--;
};
vector<int> respuestas(q);
int izq = 0, der = -1;
for (const auto& consulta : consultas) {
while (der < consulta.derecha) {
der++;
agregar(der);
}
while (izq > consulta.izquierda) {
izq--;
agregar(izq);
}
while (der > consulta.derecha) {
remover(der);
der--;
}
while (izq < consulta.izquierda) {
remover(izq);
izq++;
}
respuestas[consulta.id] = respuesta_actual;
}
for (int i = 0; i < q; ++i) {
cout << respuestas[i] << endl;
}
return 0;
}
G. Consulta de Mezcla de Rango
Se utiliza el algoritmo de Mo con descomposición en bloques para mantener el producto de ivnersos factoriales, optimizando consultas sobre permutaciones en rangos.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int TAM_BLOQUE = 500;
struct Consulta {
int izquierda, derecha, valor, id;
bool operator<(const Consulta& otra) const {
if (izquierda / TAM_BLOQUE != otra.izquierda / TAM_BLOQUE) {
return izquierda < otra.izquierda;
}
if ((izquierda / TAM_BLOQUE) % 2 == 1) {
return derecha > otra.derecha;
}
return derecha < otra.derecha;
}
};
int main() {
int n, q;
cin >> n >> q;
vector<int> arreglo(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> arreglo[i];
}
int max_valor = *max_element(arreglo.begin() + 1, arreglo.end());
vector<ll> factorial(n + 1, 1);
vector<ll> inv_factorial(n + 1, 1);
vector<ll> inverso(n + 1, 1);
for (int i = 1; i <= n; ++i) {
factorial[i] = factorial[i - 1] * i % MOD;
if (i > 1) {
inverso[i] = MOD - MOD / i * inverso[MOD % i] % MOD;
}
inv_factorial[i] = inv_factorial[i - 1] * inverso[i] % MOD;
}
int num_bloques = (max_valor + TAM_BLOQUE - 1) / TAM_BLOQUE;
vector<int> conteo(max_valor + 1, 0);
vector<ll> producto_bloque(num_bloques, 1);
vector<int> suma_bloque(num_bloques, 0);
auto actualizar = [&](int valor, int delta) {
int bloque = valor / TAM_BLOQUE;
producto_bloque[bloque] = producto_bloque[bloque] * inverso[conteo[valor] + 1] % MOD * factorial[conteo[valor]] % MOD;
conteo[valor] += delta;
suma_bloque[bloque] += delta;
producto_bloque[bloque] = producto_bloque[bloque] * inv_factorial[conteo[valor]] % MOD * factorial[conteo[valor] - delta] % MOD;
};
auto consulta_funcion = [&](int limite) -> ll {
ll total_elementos = 0;
ll producto_total = 1;
for (int bloque = 0; bloque < limite / TAM_BLOQUE; ++bloque) {
total_elementos += suma_bloque[bloque];
producto_total = producto_total * producto_bloque[bloque] % MOD;
}
for (int i = (limite / TAM_BLOQUE) * TAM_BLOQUE; i < limite; ++i) {
total_elementos += conteo[i];
producto_total = producto_total * inv_factorial[conteo[i]] % MOD;
}
return factorial[total_elementos] * producto_total % MOD;
};
vector<Consulta> consultas(q);
for (int i = 0; i < q; ++i) {
int l, r, x;
cin >> l >> r >> x;
consultas[i] = {l, r, x, i};
}
sort(consultas.begin(), consultas.end());
vector<ll> respuestas(q);
int izq = 1, der = 0;
for (const auto& consulta : consultas) {
while (izq > consulta.izquierda) {
izq--;
actualizar(arreglo[izq], 1);
}
while (der < consulta.derecha) {
der++;
actualizar(arreglo[der], 1);
}
while (izq < consulta.izquierda) {
actualizar(arreglo[izq], -1);
izq++;
}
while (der > consulta.derecha) {
actualizar(arreglo[der], -1);
der--;
}
respuestas[consulta.id] = consulta_funcion(consulta.valor);
}
for (int i = 0; i < q; ++i) {
cout << respuestas[i] << endl;
}
return 0;
}