A - Calculadora Simple
Observaciones clave:
- Cada operación \(x \gets x + 1\) cambia \(|x|\) en al menos 1.
- Se puede reordenar las operaciones para que todas las adiciones se ejecuten consecutivamente, ya que \(x \gets -x\) seguido de \(x \gets x + 1\) es equivalente a \(x \gets -x\) con un desplazamiento.
- No es óptimo ejecutar \(x \gets -x\) dos veces seguidas.
La secuencia óptima consiste en opcionalmente aplicar \(x \gets -x\), luego ejecutar varias adiciones, y finalmente opcionalmente aplicar \(x \gets -x\) nuevamenet. Esto permite enumerar los cuatro casos posibles para evitar ramificaciones complejas.
#include <iostream>
using namespace std;
typedef long long ll;
ll leer() {
ll valor = 0, signo = 1;
char c = cin.get();
while (!isdigit(c)) {
if (c == '-') signo = -1;
c = cin.get();
}
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor * signo;
}
void escribir(ll x) {
if (x < 0) {
cout << '-';
x = -x;
}
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
ll calcularDiferencia(int inicio, int objetivo) {
if (inicio <= objetivo) return objetivo - inicio;
else return 1e18;
}
int main() {
int inicio = leer(), objetivo = leer();
ll caso1 = calcularDiferencia(inicio, objetivo);
ll caso2 = calcularDiferencia(inicio, -objetivo) + 1;
ll caso3 = calcularDiferencia(-inicio, objetivo) + 1;
ll caso4 = calcularDiferencia(-inicio, -objetivo) + 2;
ll resultado = min(min(caso1, caso2), min(caso3, caso4));
escribir(resultado);
return 0;
}
B - Repintado Contiguo
Es evidente que la secuencia final debe contener al menos un segmento continuo de longitud \(K\) de un mismo color. Podemos considerar este segmento como \([i, i+K-1]\). Para las posiciones fuera de este segmento, es equivalente a que los valores puedan elegirse libremente, ya que el color de cada posición \(j\) se determina por la operación que cubre \([j, j+K-1]\). Por lo tanto, el problema se reduce a calcular sumas prefijas y maximizar la suma total.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX_N = 100005;
int n, k;
ll arreglo[MAX_N];
ll sumaPositiva[MAX_N], sumaTotal[MAX_N];
ll leer() {
ll valor = 0, signo = 1;
char c = cin.get();
while (!isdigit(c)) {
if (c == '-') signo = -1;
c = cin.get();
}
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor * signo;
}
void escribir(ll x) {
if (x < 0) {
cout << '-';
x = -x;
}
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
int main() {
n = leer();
k = leer();
for (int i = 1; i <= n; i++) {
arreglo[i] = leer();
sumaTotal[i] = sumaTotal[i - 1] + arreglo[i];
sumaPositiva[i] = sumaPositiva[i - 1] + max(arreglo[i], 0LL);
}
ll maxSuma = 0;
for (int i = 0; i + k <= n; i++) {
ll segmento = max(sumaTotal[i + k] - sumaTotal[i], 0LL);
ll izquierda = sumaPositiva[i];
ll derecha = sumaPositiva[n] - sumaPositiva[i + k];
maxSuma = max(maxSuma, segmento + izquierda + derecha);
}
escribir(maxSuma);
return 0;
}
C - Enlosado con Tetrominós
Al colocar tetrominós como T, S y Z, se crea una región con un número impar de celdas residuales, lo que impide colocar otras piezas (todas compuestas por cuatro celdas). Los tetrominós O pueden colocarse completamente de forma óptima. Las piezas L, J e I pueden agruparse en pares; además, tomar una de cada tipo forma un "sofá" (una estructura de \(6 \times 2\)). Si se usan dos "sofás", podemos emparejar L, J e I sin pérdida de eficiencia, por lo que solo es necesario considerar casos con 0 o 1 "sofá".
#include <iostream>
using namespace std;
typedef long long ll;
ll leer() {
ll valor = 0, signo = 1;
char c = cin.get();
while (!isdigit(c)) {
if (c == '-') signo = -1;
c = cin.get();
}
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor * signo;
}
void escribir(ll x) {
if (x < 0) {
cout << '-';
x = -x;
}
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
int main() {
ll piezas[7];
for (int i = 0; i < 7; i++) piezas[i] = leer();
ll totalO = piezas[1];
ll totalL = piezas[3] / 2 * 2;
ll totalJ = piezas[4] / 2 * 2;
ll totalI = piezas[0] / 2 * 2;
ll combinacionPar = totalL + totalJ + totalI;
ll combinacionSofa = 0;
if (piezas[3] > 0 && piezas[4] > 0 && piezas[0] > 0) {
ll lRes = (piezas[3] - 1) / 2 * 2;
ll jRes = (piezas[4] - 1) / 2 * 2;
ll iRes = (piezas[0] - 1) / 2 * 2;
combinacionSofa = lRes + jRes + iRes + 3;
}
ll maxSofas = max(combinacionPar, combinacionSofa);
escribir(totalO + maxSofas);
return 0;
}
D - K-ésimo K
Ordenamos los valores \(\{x_i\}\) de menor a mayor. Luego, insertamos greedy los elementos más pequeños siempre que, antes de insertar \(i\), el número de apariciones de \(i\) sea menor que \(i\). Los elementos restantes pueden insertarse libremente. La corrección de esta estrategia greedy es directa.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 505;
int n;
vector<int> secuencia;
vector<pair<int, int>> elementos;
queue<int> necesarios, libres;
int leer() {
int valor = 0;
char c = cin.get();
while (!isdigit(c)) c = cin.get();
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor;
}
void escribir(int x) {
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
int main() {
n = leer();
for (int i = 1; i <= n; i++) {
int valor = leer();
elementos.push_back({valor, i});
}
sort(elementos.begin(), elementos.end());
vector<int> posicion(n + 1, 0);
for (int i = 0; i < n; i++) {
posicion[elementos[i].second] = i + 1;
for (int j = 1; j < elementos[i].second; j++) {
necesarios.push(elementos[i].second);
}
}
int indice = 1;
for (int i = 0; i < n; i++) {
int valorActual = elementos[i].first;
while (indice < valorActual) {
if (!necesarios.empty()) {
secuencia.push_back(necesarios.front());
necesarios.pop();
} else if (!libres.empty()) {
secuencia.push_back(libres.front());
libres.pop();
} else {
cout << "No";
return 0;
}
indice++;
}
if (necesarios.empty() || posicion[necesarios.front()] > i + 1) {
secuencia.push_back(elementos[i].second);
for (int k = elementos[i].second + 1; k <= n; k++) {
libres.push(elementos[i].second);
}
} else {
cout << "No";
return 0;
}
}
while (indice <= n * n) {
if (!libres.empty()) {
secuencia.push_back(libres.front());
libres.pop();
}
indice++;
}
cout << "Yes" << endl;
for (int elem : secuencia) {
escribir(elem);
cout << ' ';
}
return 0;
}
E - Siguiente o Siguiente-Siguiente
Para la permutación \(\{p_i\}\), construimos un grafo dirigido con aristas \((i, p_i)\), que forma una unión de ciclos. Para el arreglo \(\{a_i\}\), el grafo resultante es un bosque de árboles con ciclos dirigidos. Cada punto puede tomar \(a_i = p_i\) o \(a_i = p_{p_i}\), lo que equivale a avanzar uno o dos pasos en el grafo original. Se analizan varios casos para los ciclos y los árboles, calculando el número de configuraciones posibles usando combinatoria y progrmaación dinámica.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MODULO = 1e9 + 7;
const int MAX_N = 100005;
int n;
int asignacion[MAX_N];
bool visitado[MAX_N];
vector<int> predecesores[MAX_N];
int conteoCiclos[MAX_N];
ll factorial[MAX_N], inversoFactorial[MAX_N];
ll leer() {
ll valor = 0, signo = 1;
char c = cin.get();
while (!isdigit(c)) {
if (c == '-') signo = -1;
c = cin.get();
}
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor * signo;
}
void escribir(ll x) {
if (x < 0) {
cout << '-';
x = -x;
}
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
ll potenciaRapida(ll base, ll exponente) {
ll resultado = 1;
while (exponente) {
if (exponente & 1) resultado = resultado * base % MODULO;
base = base * base % MODULO;
exponente >>= 1;
}
return resultado;
}
ll combinatoria(ll total, ll elegir) {
if (total < elegir || elegir < 0) return 0;
return factorial[total] * inversoFactorial[elegir] % MODULO * inversoFactorial[total - elegir] % MODULO;
}
int main() {
n = leer();
factorial[0] = inversoFactorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i % MODULO;
inversoFactorial[i] = potenciaRapida(factorial[i], MODULO - 2);
asignacion[i] = leer();
predecesores[asignacion[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (predecesores[i].size() > 2) {
escribir(0);
return 0;
}
if (predecesores[i].size() == 2) {
int rama1 = predecesores[i][0], rama2 = predecesores[i][1];
int longitud1 = 1, longitud2 = 1;
while (predecesores[rama1].size() == 1) {
visitado[rama1] = true;
rama1 = predecesores[rama1][0];
longitud1++;
}
while (predecesores[rama2].size() == 1) {
visitado[rama2] = true;
rama2 = predecesores[rama2][0];
longitud2++;
}
if (predecesores[rama1].size() == 2 && predecesores[rama2].size() == 2) {
escribir(0);
return 0;
}
if (predecesores[rama1].size() == 2) swap(longitud1, longitud2);
if (longitud1 > longitud2) {
escribir(0);
return 0;
}
visitado[i] = visitado[rama1] = visitado[rama2] = true;
}
}
ll resultado = 1;
for (int i = 1; i <= n; i++) {
if (visitado[i]) continue;
int nodoActual = i;
int longitudCiclo = 0;
while (!visitado[nodoActual]) {
if (predecesores[nodoActual].empty()) {
escribir(0);
return 0;
}
visitado[nodoActual] = true;
nodoActual = predecesores[nodoActual][0];
longitudCiclo++;
}
conteoCiclos[longitudCiclo]++;
}
ll sumaPares = 0;
ll factorPar = 1;
for (int pares = 0; pares <= conteoCiclos[1]; pares += 2) {
sumaPares = (sumaPares + factorPar * combinatoria(conteoCiclos[1], pares) % MODULO) % MODULO;
factorPar = factorPar * (pares + 1) % MODULO;
}
resultado = resultado * sumaPares % MODULO;
for (int longitud = 2; longitud <= n; longitud++) {
if (conteoCiclos[longitud] == 0) continue;
ll contribucion = 0;
ll factorLocal = 1;
for (int pares = 0; pares <= conteoCiclos[longitud]; pares += 2) {
ll multiplicador = 1;
if (longitud % 2 == 1 && longitud > 1) {
multiplicador = potenciaRapida(2, conteoCiclos[longitud] - pares);
}
ll potenciaLongitud = potenciaRapida(longitud, pares / 2);
contribucion = (contribucion + multiplicador * potenciaLongitud % MODULO * factorLocal % MODULO * combinatoria(conteoCiclos[longitud], pares) % MODULO) % MODULO;
factorLocal = factorLocal * (pares + 1) % MODULO;
}
resultado = resultado * contribucion % MODULO;
}
escribir(resultado);
cout << endl;
return 0;
}
F - Radio Negro
Definimos \(S_{u,d}\) como el conjunto de puntos a distancia no mayor que \(d\) de \(u\). Para contar sin duplicados, consideramos la configuración óptima donde \(d\) es mínimo. Se demuestra que para un conjunto \(S\) distinto de todos los puntos, el punto \(u\) que minimiza \(d\) es único. Usamos programación dinámica en árboles con cambio de raíz para calcular el rango válido de \(d\) para cada nodo, asegurando que los conjuntos \(S_{u,d}\) sean válidos y contabilizando las configuraciones posibles.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 200005;
const int INFINITO = 1e9;
int n;
int esNegro[MAX_N];
int profundidadMaxima[MAX_N];
int totalNegros[MAX_N];
ll contadorTotal = 0;
vector<int> grafo[MAX_N];
ll leer() {
ll valor = 0, signo = 1;
char c = cin.get();
while (!isdigit(c)) {
if (c == '-') signo = -1;
c = cin.get();
}
while (isdigit(c)) {
valor = valor * 10 + (c - '0');
c = cin.get();
}
return valor * signo;
}
void escribir(ll x) {
if (x < 0) {
cout << '-';
x = -x;
}
if (x > 9) escribir(x / 10);
cout << static_cast<char>(x % 10 + '0');
}
void dfsProfundidad(int nodo, int padre) {
totalNegros[nodo] = esNegro[nodo];
for (int hijo : grafo[nodo]) {
if (hijo != padre) {
dfsProfundidad(hijo, nodo);
profundidadMaxima[nodo] = max(profundidadMaxima[nodo], profundidadMaxima[hijo] + 1);
totalNegros[nodo] += totalNegros[hijo];
}
}
}
void dfsCalculo(int nodo, int padre, int profundidadPadre) {
int maxima1 = -1, maxima2 = -1;
int minimoHijo = (totalNegros[1] == totalNegros[nodo] ? INFINITO : profundidadPadre);
for (int hijo : grafo[nodo]) {
if (hijo != padre) {
if (profundidadMaxima[hijo] > maxima1) {
maxima2 = maxima1;
maxima1 = profundidadMaxima[hijo];
} else {
maxima2 = max(maxima2, profundidadMaxima[hijo]);
}
if (totalNegros[hijo] > 0) {
minimoHijo = min(minimoHijo, profundidadMaxima[hijo]);
}
}
}
for (int hijo : grafo[nodo]) {
if (hijo != padre) {
int nuevaProfundidadPadre = max(profundidadMaxima[hijo] == maxima1 ? maxima2 : maxima1, profundidadPadre) + 1;
dfsCalculo(hijo, nodo, nuevaProfundidadPadre);
}
}
if (profundidadPadre > maxima1) {
maxima2 = maxima1;
maxima1 = profundidadPadre;
} else {
maxima2 = max(maxima2, profundidadPadre);
}
int limiteSuperior = min(maxima1, maxima2 + 2);
int limiteInferior = esNegro[nodo] ? -1 : minimoHijo;
if (limiteSuperior > limiteInferior) {
contadorTotal += limiteSuperior - limiteInferior;
}
}
int main() {
n = leer();
for (int i = 1; i < n; i++) {
int u = leer(), v = leer();
grafo[u].push_back(v);
grafo[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
char c = cin.get();
while (!isdigit(c)) c = cin.get();
esNegro[i] = c - '0';
}
dfsProfundidad(1, 0);
dfsCalculo(1, 0, -INFINITO);
escribir(contadorTotal + 1);
return 0;
}