Descripción: Hay \(N\) bolsas de galletas, cada una con \(A_i\) galletas. Se deben seleccionar algunas bolsas para comer todas las galletas, de modo que el total sea congruente con \(P\) módulo 2. Encuentra el número de formas de selección posibles.
Solución
Se utiliza combinatoria para resolverlo. Para \(P=1\), las bolsas con número par de galletas puedan seleccionarse arbitrariamente, y para las impares se deben elegir un número impar de ellas. Para \(P=0\), se elige un número par de bolsas impares. El cálculo de combinaciones se realiza de forma iterativa para evitar desbordamientos. Dado que \(N \leq 50\), es factible calcular directamente.
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
ull calcular_combinacion(ull n, ull m) {
if (m == 0) return 1;
ull resultado = 1;
for (ull i = 1; i <= n - m; ++i)
resultado = resultado * (i + m) / i;
return resultado;
}
int main() {
int n, p;
scanf("%d %d", &n, &p);
int conteo_par = 0, conteo_impar = 0;
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
if (x % 2 == 0) conteo_par++;
else conteo_impar++;
}
ull total = 0;
if (p == 0) {
for (int i = 0; i <= conteo_impar; i += 2)
total += calcular_combinacion(conteo_impar, i);
} else {
for (int i = 1; i <= conteo_impar; i += 2)
total += calcular_combinacion(conteo_impar, i);
}
total <<= conteo_par;
printf("%llu\n", total);
return 0;
}
B - Diferencias Moderadas
Descripción: Hay \(N\) casillas en una fila, con valores \(A\) y \(B\) en los extremos. Se deben llenar las casillas vacías con enteros tal que la diferencia absoluta entre casillas adyacentes esté entre \(C\) y \(D\). Determina si es posible.
Solución
Se modela el problema mediante desigualdades. Sea \(m\) el número de pasos con diferencia negativa. Al sumar todas las diferencias, se obtiene \(B-A\). Por lo tanto, se verifica si existe un \(m\) tal que \(C \times (n-m-1) - D \times m \leq B-A \leq D \times (n-m-1) - C \times m\). Se itera sobre posibles valores de \(m\) para comprobar la condición.
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ll n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
bool factible = false;
for (ll m = 1; m <= n; ++m) {
ll inferior = c * (n - m - 1) - d * m;
ll superior = (n - m - 1) * d - c * m;
if (inferior <= b - a && b - a <= superior) {
factible = true;
break;
}
}
cout << (factible ? "YES" : "NO") << endl;
return 0;
}
C - Snuke y Hechizos
Descripción: Hay \(N\) bolas en una fila, cada una con un entero \(A_i\). Al lanzar un hechizo, desaparecen todas las bolas con el número igual al conteo actual de bolas. Se requiere hacer desaparecer todas las bolas, modificando el número mínimo de enteros en las bolas. Hay \(M\) cambios en los valores de las bolas, y después de cada cambio se debe calcular el mínimo de modificaciones necesarias.
Solución
Se modela el problema cubriendo el intervalo \([0, N]\) en un eje numérico. Para cada bola con valor \(k\), se incrementa la cobertura en la posición \(k\). Si toda la cobertura se cubre, no se necesitan modificaciones. De lo contrario, la longitud no cubierta corresponde al número mínimo de modificaciones. Se utiliza un arreglo para rastrear la cobertura y se actualiza dinámicamente con los cambios.
#include <cstdio>
using namespace std;
const int MAXN = 200005;
int n, m;
int valor[MAXN];
int conteo[MAXN];
int cobertura[MAXN];
int total_cubierto = 0;
void incrementar_cobertura(int pos) {
if (pos <= 0) return;
if (++cobertura[pos] == 1) total_cubierto++;
}
void decrementar_cobertura(int pos) {
if (pos <= 0) return;
if (--cobertura[pos] == 0) total_cubierto--;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &valor[i]);
conteo[valor[i]]++;
incrementar_cobertura(valor[i] - conteo[valor[i]] + 1);
}
while (m--) {
int x, y;
scanf("%d %d", &x, &y);
decrementar_cobertura(valor[x] - conteo[valor[x]] + 1);
conteo[valor[x]]--;
conteo[y]++;
incrementar_cobertura(y - conteo[y] + 1);
valor[x] = y;
printf("%d\n", n - total_cubierto);
}
return 0;
}
D - Juego en Árbol
Descripción: Dado un árbol con \(N\) vértices, Alice y Bob juegan alternadamente eliminando aristas, removiendo el componente que no contiene al vértice raíz. El jugador que no pueda hacer un movimiento pierde. Determina el ganador con juego óptimo.
Solución
Se utiliza el teorema de Sprague-Grundy. Para un nodo, el valor SG es el XOR de los valores SG de sus hijos incrementados en 1. El valor SG del árbol raíz determina el ganador: si es no cero, Alice gana; si es cero, Bob gana. Se realiza un DFS para calcular estos valores.
#include <vector>
using namespace std;
vector<int> adyacencia[100005];
int calcular_sg(int nodo, int padre) {
int sg = 0;
for (int hijo : adyacencia[nodo]) {
if (hijo != padre) {
sg ^= calcular_sg(hijo, nodo) + 1;
}
}
return sg;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
int u, v;
scanf("%d %d", &u, &v);
adyacencia[u].push_back(v);
adyacencia[v].push_back(u);
}
int sg_raiz = calcular_sg(1, -1);
printf("%s\n", sg_raiz ? "Alice" : "Bob");
return 0;
}
E - Rompecabezas
Descripción: Se tienen \(N\) piezas de rompecabezas irregulares, cada una con partes central, izquierda y derecha de alturas específicas. Deben colocarse en una mesa cuadrada siguiendo condiciones: la parte central toca el borde frontal, y las otras partes tocan el borde o la parte superior de otras piezas. Determina si es posible una disposición válida.
Solución
Se modela el problema como un grafo dirigido donde los nodos representan alturas. Cada pieza define un borde desde una altura izquierda a una derecha. La condición de disposición se reduce a verificar que el grafo pueda descomponerse en caminos que comiencen en nodos positivos y terminen en nodos negativos. Se usa Union-Find y se verifican desigualdades de grado.
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXH = 205;
int padre[MAXH * 2];
int gr_entrada[MAXH * 2];
int gr_salida[MAXH * 2];
bool visitado[MAXH * 2];
int encontrar(int x) {
if (padre[x] != x) padre[x] = encontrar(padre[x]);
return padre[x];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i <= 2 * m; ++i) {
padre[i] = i;
visitado[i] = false;
}
for (int i = 0; i < n; ++i) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
int izquierda = (c > 0) ? -c : a;
int derecha = (d > 0) ? d : -b;
izquierda += m;
derecha += m;
if (encontrar(izquierda) != encontrar(derecha))
padre[encontrar(izquierda)] = encontrar(derecha);
gr_entrada[derecha]++;
gr_salida[izquierda]++;
}
for (int i = 0; i < m; ++i) {
if (gr_salida[i] > gr_entrada[i]) {
printf("NO\n");
return 0;
}
}
for (int i = m + 1; i <= 2 * m; ++i) {
if (gr_salida[i] < gr_entrada[i]) {
printf("NO\n");
return 0;
}
}
for (int i = 0; i <= 2 * m; ++i) {
if (gr_entrada[i] != gr_salida[i])
visitado[encontrar(i)] = true;
}
for (int i = 0; i <= 2 * m; ++i) {
if (gr_entrada[i] && gr_salida[i] && !visitado[encontrar(i)]) {
printf("NO\n");
return 0;
}
}
printf("YES\n");
return 0;
}
F - Zigzag
Descripción: Hay un triángulo equilátero con \(N\) capas. Se deben dibujar \(M\) líneas poligonales desde el vértice superior, moviéndose hacia abajo-izquierda o abajo-derecha en cada paso. Las líneas deben estar ordenadas de izquierda a derecha, y hay \(K\) restricciones en los movimientos específicos. Calcula el número de formas módulo \(10^9+7\).
Solución
Se utiliza programación dinámica con compresión de estados. Cada estado rerpesenta una configuración de movimientos en una capa. Las restricciones se manejan al forzar ciertos movimientos. Se optimiza la transición al notar que solo se necesita rastrear la posición más a la izquierda permitida, y se actualizan los estados de manera eficiente usando operaciones a nivel de bits.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 20;
int n, m, k;
int restriccion[MAXN][MAXN];
int dp[2][1 << MAXN];
int principal() {
scanf("%d %d %d", &n, &m, &k);
n--;
memset(restriccion, 0, sizeof(restriccion));
for (int i = 0; i < k; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
restriccion[a][b - 1] = c + 1;
}
dp[0][0] = 1;
int estado_actual = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < n; ++j) {
estado_actual ^= 1;
memset(dp[estado_actual], 0, sizeof(dp[estado_actual]));
for (int mascara = 0; mascara < (1 << n); ++mascara) {
if (!dp[estado_actual ^ 1][mascara]) continue;
if (restriccion[i][j] != 2 && ((mascara >> j) & 1) == 0) {
dp[estado_actual][mascara] = (dp[estado_actual][mascara] + dp[estado_actual ^ 1][mascara]) % MOD;
}
if (restriccion[i][j] != 1) {
int nueva_mascara;
if ((mascara >> j) & 1) {
nueva_mascara = mascara;
} else {
int bits_superiores = mascara & (~((1 << (j + 1)) - 1));
int bit_menor = bits_superiores & (-bits_superiores);
nueva_mascara = mascara ^ (1 << j) ^ bit_menor;
}
dp[estado_actual][nueva_mascara] = (dp[estado_actual][nueva_mascara] + dp[estado_actual ^ 1][mascara]) % MOD;
}
}
}
}
int total = 0;
for (int mascara = 0; mascara < (1 << n); ++mascara)
total = (total + dp[estado_actual][mascara]) % MOD;
printf("%d\n", total);
return 0;
}