Enunciado:
Se tiene un total de sum(a[i]) artículos, donde a[i] representa la cantidad de artículos que tienen exactamente i citas. Se debe encontrar el valor máximo h tal que al menos h artículos tengan cada uno al menos h citas.
Enfoque:
Utilizamos búsqueda binaria para determinar el valor óptimo de h. Es crucial interpretar correctamente la relación entre el índice i y el valor a[i]. La función de verificación comprueba si para un valor h dado, existen suficientes artículos con al menos h citas.
Implementación:
#include <bits>
using namespace std;
typedef long long LL;
const int MAXN = 200007;
const LL INF = 1e18;
int n;
int citations[MAXN];
bool verificar(LL h) {
LL total = 0;
for(int i = 0; i <= n; i++) {
if(i >= h) total += citations[i];
}
return total >= h;
}
int main() {
while(scanf("%d", &n) != EOF) {
for(int i = 0; i <= n; i++) {
scanf("%d", &citations[i]);
}
LL limiteSuperior = INF, limiteInferior = 0, medio, respuesta = 0;
while(limiteSuperior >= limiteInferior) {
medio = (limiteSuperior + limiteInferior) >> 1;
if(verificar(medio)) {
limiteInferior = medio + 1;
respuesta = medio;
} else {
limiteSuperior = medio - 1;
}
}
printf("%lld\n", respuesta);
}
return 0;
}
</bits>
Problema B
Enunciado:
Se dispone de n horas. Si se invierten x horas en escribir un artículo, este recibirá x*a citas. Se debe calcular el h-index resultante.
Enfoque:
El aálisis de los ejemplos muestra que la estrategia óptima es asignar exactamente 1 hora por artículo. Esto produce n artículos con números de citas a, a+1, a+2, ..., a+n-1. Para un valor h, la posición correspondiente en la secuencia es h-a+1 (índice 1-based), y la cantidad de elementos ≥ h es n-h+a. Por definición de h-index, n-h+a ≥ h, lo que implica h ≤ (n+a)/2. El valor máximo es entonces (n+a)/2.
Implementación:
#include <bits>
using namespace std;
int main() {
int n, a;
while(scanf("%d%d", &n, &a) != EOF) {
printf("%d\n", (n + a) / 2);
}
return 0;
}
</bits>
Problema C
Enunciado:
Dado un rango [Li, Ri], se debe calcular el h-index correspondiente a ese rango.
Enfoque:
Para cada consulta, realizamos una búsqueda binaria del valor h. Verificamos si el (h+1)-ésimo elemento más grande es ≥ h. Este problema se resuelve eficientemente utilizando un árbol de segmento persistente (Persistent Segment Tree), que permite consultas de rangos en versiones anteriores de la estructura de datos.
Implementación:
#include <bits>
using namespace std;
typedef long long LL;
const int MAXN = 100007;
int n, q, cnt, x, y;
int valores[MAXN], raices[MAXN];
struct Nodo {
int izq, der, suma;
} arbol[MAXN * 40];
void actualizar(int izq, int der, int &nuevo, int antiguo, int pos) {
arbol[++cnt] = arbol[antiguo];
arbol[cnt].suma++;
nuevo = cnt;
if(izq == der) return;
int mid = (izq + der) >> 1;
if(mid >= pos) actualizar(izq, mid, arbol[nuevo].izq, arbol[antiguo].izq, pos);
else actualizar(mid + 1, der, arbol[nuevo].der, arbol[antiguo].der, pos);
}
int consultar(int izq, int der, int nodoIzq, int nodoDer, int k) {
if(izq == der) return izq;
int mid = (izq + der) >> 1;
int sumaIzq = arbol[arbol[nodoDer].izq].suma - arbol[arbol[nodoIzq].izq].suma;
if(sumaIzq >= k) return consultar(izq, mid, arbol[nodoIzq].izq, arbol[nodoDer].izq, k);
else return consultar(mid + 1, der, arbol[nodoIzq].der, arbol[nodoDer].der, k - sumaIzq);
}
int main() {
while(scanf("%d%d", &n, &q) != EOF) {
cnt = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &valores[i]);
actualizar(1, n, raices[i], raices[i-1], valores[i]);
}
while(q--) {
scanf("%d%d", &x, &y);
int longitud = y - x + 1;
int limiteSuperior = longitud, limiteInferior = 1, medio, respuesta = 1;
while(limiteSuperior >= limiteInferior) {
medio = (limiteSuperior + limiteInferior) >> 1;
int pos = consultar(1, n, raices[x-1], raices[y], longitud - medio + 1);
if(pos >= medio) {
limiteInferior = medio + 1;
respuesta = max(respuesta, medio);
} else {
limiteSuperior = medio - 1;
}
}
printf("%d\n", respuesta);
}
for(int i = 0; i <= cnt; i++) {
arbol[i].suma = 0;
}
}
return 0;
}
</bits>
Problema F
Enunciado:
Dado n trpiletas y un criterio de ordenamiento específico, se debe generar la secuencia ordenada de los identificadores.
Enfoque:
El problema se resuelve directamente utilizando una función de comparación personalizada en un algoritmo de ordenamiento. Es crucial manejar adecuadamente la precisión numérica para evitar errores. Una estrategia efectiva es simplificar las expresiones comparativas para evitar operaciones de punto flotante.
Implementación:
#include <bits>
using namespace std;
int n;
struct Tripleta {
int id;
LL a, b, c;
bool operator < (const Tripleta &otra) const {
return (a + b) * otra.c == (otra.a + otra.b) * c ?
id < otra.id :
(a + b) * otra.c < (otra.a + otra.b) * c;
} tripletas[MAXN];
int main() {
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; i++) {
tripletas[i].id = i;
scanf("%lld%lld%lld", &tripletas[i].a, &tripletas[i].b, &tripletas[i].c);
}
sort(tripletas + 1, tripletas + n + 1);
for(int i = 1; i <= n; i++) {
printf("%d%c", tripletas[i].id, i == n ? '\n' : ' ');
}
}
return 0;
}
</bits>
Problema G
Enunciado:
Dadas dos cadenas s y t, se permite realizar operaciones de eliminación o inserción de los patrones "aa", "bb" y "abab" en cualquier posición. Se debe determinar si es posible transformar s en t mediante cualquier secuencia de estas operaciones.
Enfoque:
Los ejemplos indican que las letras 'a' y 'b' pueden intercambiar posiciones, pero no pueden intercambiarse con 'c'. La estrategia consiste usar 'c' como delimitador y verificar, para cada segmento entre caracteres 'c', si la paridad de la cantidad de 'a's y 'b's coincide entre s y t.
Implementación:
#include <bits>
using namespace std;
string cadena1, cadena2;
char s[MAXN], t[MAXN];
int main() {
while(scanf("%s%s", s, t) != EOF) {
int n = strlen(s), m = strlen(t);
cadena1.clear(); cadena2.clear();
int numA = 0, numB = 0;
for(int i = 0; i < n; i++) {
if(s[i] == 'a') {
numA = (numA + 1) % 2;
} else if(s[i] == 'b') {
numB = (numB + 1) % 2;
} else {
if(numA) cadena1 += 'a';
if(numB) cadena1 += 'b';
cadena1 += 'c';
numA = numB = 0;
}
}
if(numA) cadena1 += 'a';
if(numB) cadena1 += 'b';
numA = numB = 0;
for(int i = 0; i < m; i++) {
if(t[i] == 'a') {
numA = (numA + 1) % 2;
} else if(t[i] == 'b') {
numB = (numB + 1) % 2;
} else {
if(numA) cadena2 += 'a';
if(numB) cadena2 += 'b';
cadena2 += 'c';
numA = numB = 0;
}
}
if(numA) cadena2 += 'a';
if(numB) cadena2 += 'b';
if(cadena1 == cadena2) puts("Yes");
else puts("No");
}
return 0;
}
</bits>
Problema K
Enunciado:
Dados los intervalos [a,b] y [c,d], se debe contar el número de pares (x,y) con x ∈ [a,b] y y ∈ [c,d] tales que x*y % 2018 = 0.
Enfoque:
La solución utiliza enumeración sistemática combinada con el principio de inclusión-exclusión para contar eficientemente los pares válidos sin recorrer todos los posibles valores.
Implementación:
#include <bits>
using namespace std;
typedef long long LL;
int a, b, c, d;
int main() {
while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF) {
LL resultado = 1LL * (b - a + 1) * (d / 2018 - (c - 1) / 2018);
resultado += 1LL * (b / 2 - (a - 1) / 2 - (b / 2018 - (a - 1) / 2018)) *
(d / 1009 - (c - 1) / 1009 - (d / 2018 - (c - 1) / 2018));
resultado += 1LL * (b / 1009 - (a - 1) / 1009 - (b / 2018 - (a - 1) / 2018)) *
(d / 2 - (c - 1) / 2 - (d / 2018 - (c - 1) / 2018));
resultado += 1LL * (b / 2018 - (a - 1) / 2018) *
(d - c + 1 - (d / 2018 - (c - 1) / 2018));
printf("%lld\n", resultado);
}
return 0;
}
</bits>