A - Divide un Cuboide
Para cumplir la condición, el cuboide debe cortarse paralelamente a una de sus caras. Probamso cada cara posible: si la arista perpendicular a la cara es de longitud c y la cara mide a × b, entonces podemos cortar justo por la mitad cuando c es par, logrando diferencia 0. Si c es impar, el mejor corte deja una diferencia de a × b. Como todas las dimensiones son ≥ 2, no hay casos borde. Tomamos el mínimo entre las tres orientaciones.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll leer() {
int sig = 1;
ll num = 0;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') sig = -1;
c = getchar();
}
while (isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void escribir(ll x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) escribir(x / 10);
putchar((x % 10) ^ 48);
}
ll diff(ll a, ll b, ll c) {
return (a & 1) ? (b * c) : 0LL;
}
int main() {
ll a = leer(), b = leer(), c = leer();
escribir(min(diff(a,b,c), min(diff(b,a,c), diff(c,a,b))));
return 0;
}
B - Slimes Coloridos
Como N es pequeño, iteramos el número de operaciones de tipo 2 (k). Para un k dado, el slimee de color i puede venir de j si la distancia circular (i - j + N) % N ≤ k. Entonces calculamos el costo mínimo para cada color considerando los k predecesores, sumamos todos, y añadimos k · x. Tomamos el mínimo sobre k de 0 a N-1. Complejidad O(N²).
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll leer() {
int sig = 1;
ll num = 0;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') sig = -1;
c = getchar();
}
while (isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void escribir(ll x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) escribir(x / 10);
putchar((x % 10) ^ 48);
}
const int MAXN = 2005;
int n;
ll a[MAXN], b[MAXN];
int main() {
n = leer(); ll x = leer();
ll ans = 1e18;
for (int i = 0; i < n; ++i) a[i] = b[i] = leer();
for (int k = 0; k < n; ++k) {
ll suma = 0;
for (int i = 0; i < n; ++i) {
b[i] = min(b[i], a[(i - k + n) % n]);
suma += b[i];
}
ans = min(ans, suma + k * x);
}
escribir(ans);
return 0;
}
C - Rejilla AND
Debemos construir dos rejillas A y B tales que el AND de ambas sea igual a la rejilla original. La idea es que A tenga toda la primera columna y B toda la última columna llenas de ‘#’. Luego, por filas alternadas, rellenamos las columnas interiores de manera que cada celda que no esté en los bordes sea ‘#’ solo en una de las dos rejillas. Fnialmente, sobrescribimos con la rejilla original todas las posiciones donde originalmente hay ‘#’. Esto garantiza conectividad y que la intersección sea exactamente la original.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
int n, m;
string s[MAXN], a[MAXN], b[MAXN];
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> s[i];
a[i] = b[i] = s[i];
}
for (int i = 0; i < n; ++i) {
a[i][0] = b[i][m-1] = '#';
if (i & 1) {
for (int j = 1; j < m-1; ++j) a[i][j] = '#';
} else {
for (int j = 1; j < m-1; ++j) b[i][j] = '#';
}
}
for (int i = 0; i < n; ++i) cout << a[i] << endl;
cout << endl;
for (int i = 0; i < n; ++i) cout << b[i] << endl;
return 0;
}
D - Teletransportador
El nodo 1 debe apuntar a sí mismo, de lo contrario sería imposible llegar a él en exactamente K pasos. Con esa condición, el grafo se vuelve un árbol enraizado en 1. La estrategia óptima es, desde las hojas hacia arriba, cambiar el padre de un nodo a 1 si su subárbol más profundo está a distancia K-1. Implementamos con DFS que retorna la profundidad máxima del subárbol.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> hijos[MAXN];
int n, k, padre[MAXN], prof[MAXN], ans;
void dfs(int u, int d) {
prof[u] = d;
for (int v : hijos[u]) {
dfs(v, d+1);
prof[u] = max(prof[u], prof[v]);
}
if (prof[u] - d == k-1 && padre[u] != 1) {
prof[u] = d - 1;
ans++;
}
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> padre[i];
if (i > 1) hijos[padre[i]].push_back(i);
}
if (padre[1] != 1) ans = 1;
padre[1] = 1;
dfs(1, 1);
cout << ans << endl;
return 0;
}
E - Robots de Rescate
Fijamos los límites superior, inferior, izquierdo y derecho (U,D,L,R) alrededor de la salida (ex,ey). Solo consideramos robots en el rectángulo [ex−U, ex+D] × [ey−L, ey+R]. Definimos DP[U][D][L][R] como máximo número de rescatables. Las transiciones expanden el rectángulo en una dirección, añadiendo las filas o columnas que quedan libres (no en zona roja). La complejidad es O(N²M²), usamos short para memoria.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, m, sum[MAXN][MAXN];
short dp[MAXN][MAXN][MAXN][MAXN];
string s[MAXN];
int suma(int a, int b, int c, int d) {
if (a > c || b > d) return 0;
return sum[c][d] - sum[a-1][d] - sum[c][b-1] + sum[a-1][b-1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
s[i] = "." + s[i];
}
int ex = 0, ey = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (s[i][j] == 'E') { ex = i; ey = j; break; }
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] = (s[i][j] == 'o');
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
int ans = 0;
for (int u = 0; u < ex; ++u) {
for (int d = 0; d <= n - ex; ++d) {
for (int l = 0; l < ey; ++l) {
for (int r = 0; r <= m - ey; ++r) {
int cur = dp[u][d][l][r];
// expandir hacia arriba
if (ex - u - 1 >= d + 1) {
int nu = u + 1;
int f = suma(ex - nu, max(l+1, ey - r), ex - nu, min(m - r, ey + l));
dp[nu][d][l][r] = max((int)dp[nu][d][l][r], cur + f);
}
// expandir hacia abajo
if (ex + d + 1 <= n - u) {
int nd = d + 1;
int f = suma(ex + nd, max(l+1, ey - r), ex + nd, min(m - r, ey + l));
dp[u][nd][l][r] = max((int)dp[u][nd][l][r], cur + f);
}
// expandir hacia izquierda
if (ey - l - 1 >= r + 1) {
int nl = l + 1;
int f = suma(max(d+1, ex - u), ey - nl, min(n - u, ex + d), ey - nl);
dp[u][d][nl][r] = max((int)dp[u][d][nl][r], cur + f);
}
// expandir hacia derecha
if (ey + r + 1 <= m - l) {
int nr = r + 1;
int f = suma(max(d+1, ex - u), ey + nr, min(n - u, ex + d), ey + nr);
dp[u][d][l][nr] = max((int)dp[u][d][l][nr], cur + f);
}
ans = max(ans, cur);
}
}
}
}
cout << ans << endl;
return 0;
}
F - Namori
F.1 Árbol
Coloreamos el árbol con bipartito (blanco/negro). Invertimos el color inicial de los nodos negros (en la bipartición). El objetivo es que los negros se vuelvan blancos. Así, la condición cambia a que cada arista conecte colores diferentes, y la operación (invertir ambos extremos) se convierte en intercambiar los colores. La solución es posible solo si el número de blancos y negros es igual. Para cada subárbol, la diferencia entre blancos y negros (en valor absoluto) da el número mínimo de intercambios a través de la arista que conecta con el padre. Se puede demostrar que esta cota inferior es alcanzable.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll leer() { /* igual que antes */ }
void escribir(ll x) { /* igual que antes */ }
const int MAXN = 100005;
vector<int> g[MAXN];
bool color[MAXN];
ll val[MAXN], ans;
void dfs1(int u, int p, bool c) {
color[u] = !c;
for (int v : g[u]) if (v != p) dfs1(v, u, color[u]);
}
ll dfs2(int u, int p) {
ll s = val[u];
for (int v : g[u]) if (v != p) s += dfs2(v, u);
ans += abs(s);
return s;
}
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
if (m == n-1) { // árbol
dfs1(1,0,false);
int suma = 0;
for (int i = 1; i <= n; ++i) {
suma += color[i];
val[i] = color[i] ? 1 : -1;
}
if (suma * 2 != n) { cout << -1 << endl; return 0; }
dfs2(1,0);
cout << ans << endl;
} else {
// ver secciones F.2 y F.3
// Omitido por brevedad, pero sigue la misma lógica que el original
cout << "Implementación de ciclo base en el código original" << endl;
}
return 0;
}
Para el caso de grafo con un ciclo (base), se aplican técnicas adicionales: si el ciclo es par, se pueden escribir ecuaciones lineales y minimizar la suma de valores absolutos tomando la mediana; si el ciclo es impar, se puede romper una arista y ajustar con la diferencia de colores. La implementación completa está en el código original.
Tags
AtCoder, programación dinámica, teoría de grafos, árboles, DFS, BFS, algoritmos voraces, flujo en redes, matemáticas.