¡Hola chicos! Muchas gracias por participar. Esta es la primera ocasión en la que el Club de Programación Competitiva (CPCFI) escribe problemas originales para un concurso parade nivel medio superior, y nos hizo muchísima ilusión que los resolvieran.↵
↵
Para quienes tengan la curiosidad, todos los protagonistas de los problemas son personas que pertenecen al CPCFI. Somos una comunidad muy unida y nos hace mucha gracia verlos como protagonistas los problemas. Esperamos que en algún momento de sus carreras consideren unirse al club, que siempre tendrá las puertas abiertas para gente que busque desafíos complicados y una comunidad unida que los apoyará incondicionalmente.↵
↵
Les deseamos lo mejor en su formación personal y profesional y esperamos verlos de nuevo en la fase final. ↵
↵
Agradecimientos especiales a [user:RacsoFractal,2026-02-17], quién hizo posible la creación de estos problemas para el concurso y me invitó a colaborar en este desafío tan grande para el CPCFI.↵
↵
También queremos agradecer a todos los testers de los problemas, que nos ayudaron a afinar detalles y a corregir errores: [user:ELeon,2026-02-19], [user:AlexJzG,2026-02-19], [user:lamocha,2026-02-19], [user:Nitter,2026-02-19], [user:salazarislas.daniel,2026-02-19], [user:Warddd,2026-02-19],[user:AldoEZ_21,2026-02-19], [user:zum,2026-02-19], [user:eve181836,2026-02-19]↵
↵
[<h3 style="color:#4D87C7;">671145A. Samuel y la G</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/A)↵
↵
<spoiler summary="Pista">↵
Itera la cadena solo una vez.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Itera la cadena y con un condicional revisa si el caracter actual es <code>'G'</code> o <code>'g'</code>, si se cumple, no imprimas ese caracter.↵
↵
Si usas Python o Java puedes usar el método <code>.replace()</code> y sustituir las <code>'G'</code> y <code>'g'</code> con el caracter vacío <code>''</code>↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<string.h>↵
↵
#define or ||↵
↵
void solve(){↵
int n; scanf("%d",&n);↵
char str[n+1];↵
scanf("%s",str);↵
↵
for(int i=0; i<n; i++){↵
if(str[i] == 'G' or str[i] == 'g'){↵
continue;↵
}↵
↵
printf("%c",str[i]);↵
}↵
printf("\n");↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Código en Python">↵
~~~~~↵
n = int(input())↵
s = input()↵
↵
print(s.replace('G','').replace('g',''))↵
~~~~~↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145B. Entrenamiento de equipo II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/B)↵
↵
Este problema es de implementación. Supongamos que el input se guarda en tres arreglos: `m`, `a` y `l`, uno con el registro de cada competidor.↵
↵
La forma más lenta de hacerlo es en complejidad $O(N^2)$, si para el i-ésimo día se calcula la suma acumulada recorriendo desde el día `1` hasta el `i`. Teniendo la suma acumulada de los problemas resueltos por cada competidor hasta el i-ésimo día. Teniendo las tres sumas, se puede imprimir el nombre de cualquier miembro del equipo cuya suma acumulada sea la máxima entre los tres.↵
↵
Aunque por las restricciones del problema esta estrategia es válida, también se puede llevar la suma acumulada *in situ* para cada iteración. Otra forma de hacerlo, es aplicando la técnica *prefix sum*, que no es más que una suma de prefijos, con los arreglos.↵
↵
Sin importar la forma de ver el máximo acumulado para el i-ésimo día, para determinar al MVP del equipo basta con llevar la cuenta de cuántas veces cada miembro del equipo ha sido el miembro con mayor rendimiento. Es decir, cuando se detecte que el acumulado de alguien del equipo es el máximo de los tres hasta el día i, incrementar también su cuenta de MVP. Si para un día i, el máximo de problemas sacados por Mikel es max, pero también Arnau y Leon tienen max problemas hechos hasta el día i, el contador de MVP de los tres se incrementa.↵
↵
Teniendo estos contadores, hay que ver cuál es el mayor tras todos los días de entrenamiento e imprimir cualquiera que sea válido.↵
↵
La **complejidad final** alcanzable es $O(N)$, como se puede ver en la siguiente solución.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include <stdio.h>↵
#include <stdbool.h>↵
↵
int max(int a, int b) {↵
if ( a > b )↵
return a;↵
else↵
return b;↵
}↵
↵
int main() {↵
int n, elMayor, mvp[3] = {0,0,0};↵
char *ganadores[] = {"Mikel","Arnau","Leon"};↵
scanf("%d",&n);↵
int mikel[n], arns[n], leon[n];↵
↵
scanf("%d",&mikel[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&mikel[i]);↵
mikel[i] += mikel[i-1];↵
}↵
↵
scanf("%d",&arns[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&arns[i]);↵
arns[i] += arns[i-1];↵
}↵
↵
scanf("%d",&leon[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&leon[i]);↵
leon[i] += leon[i-1];↵
}↵
↵
for(int i = 0; i < n; i++)↵
{↵
elMayor = max( mikel[i], max(arns[i], leon[i]) );↵
bool printed = false;↵
if( mikel[i] == elMayor )↵
{↵
printf("1 ");↵
printed = true;↵
mvp[0]++;↵
}↵
if( arns[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("2 ");↵
printed = true;↵
}↵
mvp[1]++;↵
}↵
if( leon[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("3 ");↵
printed = true;↵
}↵
mvp[2]++;↵
}↵
}↵
↵
↵
elMayor = max(mvp[0], max(mvp[1],mvp[2]) );↵
for(int i = 0; i < 3; i++)↵
{↵
if( elMayor == mvp[i] )↵
{↵
printf("\n%s",ganadores[i]);↵
break;↵
}↵
}↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
↵
↵
[<h3 style="color:#4D87C7;">671145C. Lanzadardos inexperto</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/C)↵
↵
<spoiler summary="Pista 1">↵
$r = \sqrt{(x-u)^2+(y-v)^2}$↵
↵
Donde $x$ e $y$ son el centro de cualquier círculo y $u$ y $v$ son cualquier punto al que Zum tira un dardo.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Sea $r_{act}$ el radio del punto actual al centro de cualquier círculo y $r$ el radio de un círculo. Si $r_{act} <= r$, entonces el punto actual está dentro del círculo de radio $r$.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Para cada dardo que tira Zum, debemos calcular su distancia con respecto al centro de ambos círculos mediante la fórmula de la distancia euclidiana, nos evitaremos sacar la raíz cuadrada manejando el cuadrado de todos los términos. La distancia al centro del círculo grande es: $D_i^2 = (u_i - x_1)^2 + (v_i - y_1)^2$. Y la distancia al centro del círculo pequeño es $d_i^2 = (u_i - x_2)^2 + (v_i - y_2)^2$. Si $d_i^2$ es menor o igual que el radio del circulo pequeño al cuadrado, llamémosle $r_1^2$ ($d_i^2 \leq r_1^2$), se imprime <code>"YAAAAY!"</code>. Si esta condición no se cumple, revisamos la distancia al centro del círculo grande ($D_i^2 \leq r_1^2$), si se cumple, imprimimos <code>"MEH"</code>, en caso contrario, terminamos imprimiendo <code>"BUUUUU!"</code>.↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
↵
double distance(double x, double y, double h, double k) {↵
return (x - h) * (x - h) + (y - k) * (y - k);↵
}↵
↵
void solve(){↵
double r1,x1,y1; scanf("%lf %lf %lf",&r1, &x1, &y1);↵
double r2,x2,y2; scanf("%lf %lf %lf",&r2, &x2, &y2);↵
int q; scanf("%d", &q);↵
for(int i=0; i<q; i++){↵
double u,v; scanf("%lf %lf", &u,&v); ↵
if(distance(u, v, x2, y2)<= r2*r2){↵
printf("YAAAAY!\n");↵
continue;↵
}↵
↵
if(distance(u, v, x1, y1) <= r1*r1){↵
printf("MEH\n");↵
continue;↵
}↵
↵
printf("BUUUUU!\n");↵
}↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145D. El billar no es de vagos II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/D)↵
↵
Para este problema no es necesario estar familizarizado con los conceptos físicos presentados. Con leer atentamente el statement, el lector podrá hacer una serie de sustituciones entre las fórmulas brindadas que llevarán a una expresión final sencilla de programar.↵
↵
La distancia total recorrida por la bola de billar no es más que la suma de la distancia recorrida por la bola en cada tiro, lo cual se puede calcular despejando la variable 'd' de la ecuación brindada del MRUA:↵
↵
$$ d = \frac{v^2 - v_0^2}{2a} $$↵
↵
De aquí se deduce que la velocidad final es cero, pues Gus siempre espera a que la pelota se deje de mover antes de darle el siguiente golpe:↵
↵
$$ v = 0 $$↵
↵
La aceleración se puede calcular como dice en el enunciado, de la segunda ley de Newton como el cociente entre la fuerza de fricción generada entre la bola de billar y la mesa, entre la masa de la bola de billar. Sustituyendo variables tenemos que:↵
↵
$$ a = \frac{F_f}{m} = \frac{- \mu m G}{m} = - \mu G $$↵
↵
La velocidad inicial se puede calcular tal cual dice el enunciando:↵
↵
$$ v_0 = \frac{I}{m} $$↵
↵
Sustituyendo todo en el despeje de la distancia inicial, tenemos que:↵
↵
$$ d = \frac{v^2 - v_0^2}{2a} = \frac{0^2 - (\frac{I}{m})^2}{2(- \mu G)} $$↵
↵
Simplificando:↵
↵
$$ d = \frac{I^2}{2m^2 \mu G} $$↵
↵
Fórmula que ya es bastante sencilla de programar.↵
↵
Por otro lado, para calcular la distancia final de la bola de billar se pide, de nuevo, sumar el desplazamiento en los rectangulares que tuvo la bola tras cada tiro de Gus. Lo cual se puede hacer tal cual las fórmulas presentadas. ↵
↵
La precisión para este problema es muy chica, dado que no se espera que el lector esté familiarizado con el manejo de variables reales de alta precisión, como se puede ver en la siguientes soluciones, utilizar variables de tipo *float* será suficiente.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include<stdio.h>↵
#include<math.h>↵
↵
int main() {↵
int n, m_grams;↵
float mu = 1.2, G = 9.81, total_distance = 0.0, X = 0.0, Y = 0.0;↵
scanf("%d %d",&n,&m_grams);↵
float m = m_grams / 1000.0;↵
↵
for(int i = 0; i < n; i++) {↵
float I, x, y;↵
scanf("%f %f %f",&I,&x,&y);↵
float d = (I * I) / (2.0 * m * m * mu * G);↵
float norm = sqrt(x * x + y * y);↵
↵
float dx = d * (x / norm);↵
float dy = d * (y / norm);↵
↵
X += dx;↵
Y += dy;↵
↵
total_distance += d;↵
}↵
↵
printf("%.4f\n%.4f %.4f",total_distance,X,Y);↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145E. Hazlos primos II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/E)↵
↵
<spoiler summary="Pista 1">↵
Calcula la distancia de cada número a su primo más cercano simulando las dos operaciones.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Ordena esas distancias.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Primero debemos generar un arreglo del mismo tamaño que el arreglo original, es decir, tamaño $N$, llamemos a este arreglo <code>dist[N]</code>. Para cada elemento del arreglo original $a_i$, guardaremos en $dist_i$ la distancia a su primo más cercano. Vamos a dividir el número entre dos hasta llegar a cero, por cada división, vamos a revisar qué tan lejos está el número actual de un primo tanto hacia arriba como hacia abajo, mientras llevamos conteo del valor mínimo actual, es decir, si la división actual + su distancia al primo más cercano es menor que el valor que tenemos actualmente, lo actualizamos.↵
↵
Una vez que tengamos todas las distancias calculadas vamos a ordenarlas con cualquier algoritmo de ordenamiento (que no sea Bogo Sort ;D) y nuestra respuesta será ir iterando en orden este nuevo arreglo, restándole la distancia actual a nuestra $K$, que es las operaciones que tenemos disponibles.↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<stdbool.h>↵
↵
#define and &&↵
#define MAX_VAL 1050 ↵
#define ll long long↵
#define INF 200000000↵
↵
int min(int a, int b){↵
return a < b ? a : b;↵
}↵
↵
void bubbleSort(int n, int *arr){↵
for(int i=0; i<n-1; i++){↵
for(int j=0; j<n-i-1; j++){↵
if(arr[j] > arr[j+1]){↵
int tmp = arr[j];↵
arr[j] = arr[j+1];↵
arr[j+1] = tmp;↵
}↵
}↵
}↵
}↵
↵
bool isPrime(ll n){↵
if(n==1) return false;↵
if(n==2) return true;↵
if(n%2 == 0) return false;↵
↵
for(int i=3; i<n; i+=2){↵
if(n%i == 0) return false;↵
}↵
↵
return true;↵
}↵
↵
int distToPrime(int n){↵
if (isPrime(n)) return 0;↵
↵
int dist = 1;↵
while(true){↵
if (n - dist >= 2 && isPrime(n - dist)) return dist;↵
if (isPrime(n + dist)) return dist;↵
dist++;↵
}↵
}↵
↵
int distance(int n){↵
int min_cost = INF;↵
int divisions = 0;↵
while (n > 0) {↵
int cost = divisions + distToPrime(n);↵
min_cost = min(min_cost, cost);↵
↵
n /= 2;↵
divisions++;↵
}↵
↵
int zero = divisions + 2; ↵
min_cost = min(min_cost, zero);↵
↵
return min_cost;↵
}↵
↵
void solve(){↵
int n, k; ↵
scanf("%d %d", &n, &k);↵
↵
int board[n], costs[n];↵
for(int i=0; i<n; i++){↵
scanf("%d", &board[i]);↵
costs[i] = distance(board[i]);↵
}↵
↵
↵
bubbleSort(n, costs);↵
↵
↵
↵
int numPrimes = 0;↵
for(int i=0; i<n; i++){↵
if(costs[i] <= k){↵
numPrimes++;↵
k -= costs[i];↵
}else{↵
break;↵
}↵
}↵
↵
printf("%d\n", numPrimes);↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solución esperada">↵
En programación competitiva no es usual que una solución así funcione, debido a que estamos probando por fuerza bruta muchas posibles distancias, así como checar uno por uno los números primos y como cereza en el pastel, estamos usando un ordenamiento burbuja, que no es un algoritmo eficiente para ordenar. Hay muchos temas involucrados para lograr una solución eficiente para este problema. Sin embargo, describiremos la solución que nosotros esperábamos para este problema y dejamos como ejercicio para el lector la lectura sobre estos temas.↵
↵
En el caso de que los límites del problema fueran $1 \leq N,M,a_i, \leq 10^5$, la solución necesaria sería en cuanto a idea la misma, pero usaremos métodos distintos para lograrlo.↵
↵
Primero, necesitamos precomputar todos los primos hasta el elemento más grande del arreglo. Para esto se utiliza un algoritmo llamado [Criba de Eratóstenes](https://cp-algorithms-es.github.io/algebra/primos/criba-de-eratostenes.html), que nos devolverá una tabla que nos dirá si el i-ésimo número de la tabla es primo. Con el fin de consultar de forma rápida si cualquier número es primo mediante consultar la tabla.↵
↵
Con esto podremos probar las distancias a los primos de forma rápida. Para ordenar, hay múltiples algoritmos eficientes que nos permiten [ordenar](https://aprende.olimpiada-informatica.org/algoritmia-introduccion-4-coste-ordenar). En la solución del ejemplo se usa el ordenamiento por conteo (Counting Sort).↵
</spoiler>↵
↵
<spoiler summary="Código en C (solución esperada)">↵
Shoutout a [user:AlexJzG,2026-02-19] por la solución.↵
↵
~~~~~↵
#include <stdio.h>↵
↵
#define MAX 2002↵
↵
int sieve[MAX], nums[MAX], min_dist[MAX], sorted_dist[MAX];↵
↵
void get_primes() {↵
sieve[0] = sieve[1] = 1;↵
for (int i = 2; i < MAX; i++) {↵
if (sieve[i]) {↵
continue;↵
}↵
for (int j = i * 2; j < MAX; j += i) {↵
sieve[j] = 1;↵
}↵
}↵
}↵
↵
void get_min_dist() {↵
int last_prime = MAX + 100;↵
for (int i = MAX - 1; i >= 0; i--) {↵
if (sieve[i] == 0) {↵
last_prime = i;↵
}↵
if (min_dist[i] == 0) {↵
min_dist[i] = last_prime - i;↵
} else if (last_prime - i < min_dist[i]) {↵
min_dist[i] = last_prime - i;↵
}↵
}↵
last_prime = -100;↵
for (int i = 0; i < MAX; i++) {↵
if (sieve[i] == 0) {↵
last_prime = i;↵
}↵
↵
if (min_dist[i] == 0) {↵
min_dist[i] = i - last_prime;↵
} else if (i - last_prime < min_dist[i]) {↵
min_dist[i] = i - last_prime;↵
}↵
↵
if(min_dist[i/2] + 1 < min_dist[i]){↵
min_dist[i] = min_dist[i/2] + 1;↵
}↵
}↵
}↵
↵
void init() {↵
// Get primes (sieve[i] = 0 is prime)↵
get_primes();↵
↵
// Get min distance to p rimes↵
get_min_dist();↵
}↵
↵
void counting_sort() {↵
for (int i = 0; i < MAX; i++) {↵
sorted_dist[min_dist[i]] += nums[i];↵
}↵
}↵
↵
int max_primes(int m) {↵
int ans = 0;↵
for (int i = 0; i < MAX; i++) {↵
while (m >= i && sorted_dist[i] > 0) {↵
ans++;↵
m -= i;↵
sorted_dist[i]--;↵
}↵
}↵
return ans;↵
}↵
↵
int main() {↵
init();↵
int n, m, a;↵
scanf("%d %d\n", &n, &m);↵
for (int i = 0; i < n; i++) {↵
scanf("%d", &a);↵
nums[a]++;↵
}↵
counting_sort();↵
printf("%d\n", max_primes(m));↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
Para quienes tengan la curiosidad, todos los protagonistas de los problemas son personas que pertenecen al CPCFI. Somos una comunidad muy unida y nos hace mucha gracia verlos como protagonistas los problemas. Esperamos que en algún momento de sus carreras consideren unirse al club, que siempre tendrá las puertas abiertas para gente que busque desafíos complicados y una comunidad unida que los apoyará incondicionalmente.↵
↵
Les deseamos lo mejor en su formación personal y profesional y esperamos verlos de nuevo en la fase final. ↵
↵
Agradecimientos especiales a [user:RacsoFractal,2026-02-17], quién hizo posible la creación de estos problemas para el concurso y me invitó a colaborar en este desafío tan grande para el CPCFI.↵
↵
También queremos agradecer a todos los testers de los problemas, que nos ayudaron a afinar detalles y a corregir errores: [user:ELeon,2026-02-19], [user:AlexJzG,2026-02-19], [user:lamocha,2026-02-19], [user:Nitter,2026-02-19], [user:salazarislas.daniel,2026-02-19], [user:Warddd,2026-02-19],[user:AldoEZ_21,2026-02-19], [user:zum,2026-02-19], [user:eve181836,2026-02-19]↵
↵
[<h3 style="color:#4D87C7;">671145A. Samuel y la G</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/A)↵
↵
<spoiler summary="Pista">↵
Itera la cadena solo una vez.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Itera la cadena y con un condicional revisa si el caracter actual es <code>'G'</code> o <code>'g'</code>, si se cumple, no imprimas ese caracter.↵
↵
Si usas Python o Java puedes usar el método <code>.replace()</code> y sustituir las <code>'G'</code> y <code>'g'</code> con el caracter vacío <code>''</code>↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<string.h>↵
↵
#define or ||↵
↵
void solve(){↵
int n; scanf("%d",&n);↵
char str[n+1];↵
scanf("%s",str);↵
↵
for(int i=0; i<n; i++){↵
if(str[i] == 'G' or str[i] == 'g'){↵
continue;↵
}↵
↵
printf("%c",str[i]);↵
}↵
printf("\n");↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Código en Python">↵
~~~~~↵
n = int(input())↵
s = input()↵
↵
print(s.replace('G','').replace('g',''))↵
~~~~~↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145B. Entrenamiento de equipo II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/B)↵
↵
Este problema es de implementación. Supongamos que el input se guarda en tres arreglos: `m`, `a` y `l`, uno con el registro de cada competidor.↵
↵
La forma más lenta de hacerlo es en complejidad $O(N^2)$, si para el i-ésimo día se calcula la suma acumulada recorriendo desde el día `1` hasta el `i`. Teniendo la suma acumulada de los problemas resueltos por cada competidor hasta el i-ésimo día. Teniendo las tres sumas, se puede imprimir el nombre de cualquier miembro del equipo cuya suma acumulada sea la máxima entre los tres.↵
↵
Aunque por las restricciones del problema esta estrategia es válida, también se puede llevar la suma acumulada *in situ* para cada iteración. Otra forma de hacerlo, es aplicando la técnica *prefix sum*, que no es más que una suma de prefijos, con los arreglos.↵
↵
Sin importar la forma de ver el máximo acumulado para el i-ésimo día, para determinar al MVP del equipo basta con llevar la cuenta de cuántas veces cada miembro del equipo ha sido el miembro con mayor rendimiento. Es decir, cuando se detecte que el acumulado de alguien del equipo es el máximo de los tres hasta el día i, incrementar también su cuenta de MVP. Si para un día i, el máximo de problemas sacados por Mikel es max, pero también Arnau y Leon tienen max problemas hechos hasta el día i, el contador de MVP de los tres se incrementa.↵
↵
Teniendo estos contadores, hay que ver cuál es el mayor tras todos los días de entrenamiento e imprimir cualquiera que sea válido.↵
↵
La **complejidad final** alcanzable es $O(N)$, como se puede ver en la siguiente solución.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include <stdio.h>↵
#include <stdbool.h>↵
↵
int max(int a, int b) {↵
if ( a > b )↵
return a;↵
else↵
return b;↵
}↵
↵
int main() {↵
int n, elMayor, mvp[3] = {0,0,0};↵
char *ganadores[] = {"Mikel","Arnau","Leon"};↵
scanf("%d",&n);↵
int mikel[n], arns[n], leon[n];↵
↵
scanf("%d",&mikel[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&mikel[i]);↵
mikel[i] += mikel[i-1];↵
}↵
↵
scanf("%d",&arns[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&arns[i]);↵
arns[i] += arns[i-1];↵
}↵
↵
scanf("%d",&leon[0]);↵
for(int i = 1; i < n; i++)↵
{↵
scanf("%d",&leon[i]);↵
leon[i] += leon[i-1];↵
}↵
↵
for(int i = 0; i < n; i++)↵
{↵
elMayor = max( mikel[i], max(arns[i], leon[i]) );↵
bool printed = false;↵
if( mikel[i] == elMayor )↵
{↵
printf("1 ");↵
printed = true;↵
mvp[0]++;↵
}↵
if( arns[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("2 ");↵
printed = true;↵
}↵
mvp[1]++;↵
}↵
if( leon[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("3 ");↵
printed = true;↵
}↵
mvp[2]++;↵
}↵
}↵
↵
↵
elMayor = max(mvp[0], max(mvp[1],mvp[2]) );↵
for(int i = 0; i < 3; i++)↵
{↵
if( elMayor == mvp[i] )↵
{↵
printf("\n%s",ganadores[i]);↵
break;↵
}↵
}↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
↵
↵
[<h3 style="color:#4D87C7;">671145C. Lanzadardos inexperto</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/C)↵
↵
<spoiler summary="Pista 1">↵
$r = \sqrt{(x-u)^2+(y-v)^2}$↵
↵
Donde $x$ e $y$ son el centro de cualquier círculo y $u$ y $v$ son cualquier punto al que Zum tira un dardo.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Sea $r_{act}$ el radio del punto actual al centro de cualquier círculo y $r$ el radio de un círculo. Si $r_{act} <= r$, entonces el punto actual está dentro del círculo de radio $r$.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Para cada dardo que tira Zum, debemos calcular su distancia con respecto al centro de ambos círculos mediante la fórmula de la distancia euclidiana, nos evitaremos sacar la raíz cuadrada manejando el cuadrado de todos los términos. La distancia al centro del círculo grande es: $D_i^2 = (u_i - x_1)^2 + (v_i - y_1)^2$. Y la distancia al centro del círculo pequeño es $d_i^2 = (u_i - x_2)^2 + (v_i - y_2)^2$. Si $d_i^2$ es menor o igual que el radio del circulo pequeño al cuadrado, llamémosle $r_1^2$ ($d_i^2 \leq r_1^2$), se imprime <code>"YAAAAY!"</code>. Si esta condición no se cumple, revisamos la distancia al centro del círculo grande ($D_i^2 \leq r_1^2$), si se cumple, imprimimos <code>"MEH"</code>, en caso contrario, terminamos imprimiendo <code>"BUUUUU!"</code>.↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
↵
double distance(double x, double y, double h, double k) {↵
return (x - h) * (x - h) + (y - k) * (y - k);↵
}↵
↵
void solve(){↵
double r1,x1,y1; scanf("%lf %lf %lf",&r1, &x1, &y1);↵
double r2,x2,y2; scanf("%lf %lf %lf",&r2, &x2, &y2);↵
int q; scanf("%d", &q);↵
for(int i=0; i<q; i++){↵
double u,v; scanf("%lf %lf", &u,&v); ↵
if(distance(u, v, x2, y2)<= r2*r2){↵
printf("YAAAAY!\n");↵
continue;↵
}↵
↵
if(distance(u, v, x1, y1) <= r1*r1){↵
printf("MEH\n");↵
continue;↵
}↵
↵
printf("BUUUUU!\n");↵
}↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145D. El billar no es de vagos II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/D)↵
↵
Para este problema no es necesario estar familizarizado con los conceptos físicos presentados. Con leer atentamente el statement, el lector podrá hacer una serie de sustituciones entre las fórmulas brindadas que llevarán a una expresión final sencilla de programar.↵
↵
La distancia total recorrida por la bola de billar no es más que la suma de la distancia recorrida por la bola en cada tiro, lo cual se puede calcular despejando la variable 'd' de la ecuación brindada del MRUA:↵
↵
$$ d = \frac{v^2 - v_0^2}{2a} $$↵
↵
De aquí se deduce que la velocidad final es cero, pues Gus siempre espera a que la pelota se deje de mover antes de darle el siguiente golpe:↵
↵
$$ v = 0 $$↵
↵
La aceleración se puede calcular como dice en el enunciado, de la segunda ley de Newton como el cociente entre la fuerza de fricción generada entre la bola de billar y la mesa, entre la masa de la bola de billar. Sustituyendo variables tenemos que:↵
↵
$$ a = \frac{F_f}{m} = \frac{- \mu m G}{m} = - \mu G $$↵
↵
La velocidad inicial se puede calcular tal cual dice el enunciando:↵
↵
$$ v_0 = \frac{I}{m} $$↵
↵
Sustituyendo todo en el despeje de la distancia inicial, tenemos que:↵
↵
$$ d = \frac{v^2 - v_0^2}{2a} = \frac{0^2 - (\frac{I}{m})^2}{2(- \mu G)} $$↵
↵
Simplificando:↵
↵
$$ d = \frac{I^2}{2m^2 \mu G} $$↵
↵
Fórmula que ya es bastante sencilla de programar.↵
↵
Por otro lado, para calcular la distancia final de la bola de billar se pide, de nuevo, sumar el desplazamiento en los rectangulares que tuvo la bola tras cada tiro de Gus. Lo cual se puede hacer tal cual las fórmulas presentadas. ↵
↵
La precisión para este problema es muy chica, dado que no se espera que el lector esté familiarizado con el manejo de variables reales de alta precisión, como se puede ver en la siguientes soluciones, utilizar variables de tipo *float* será suficiente.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include<stdio.h>↵
#include<math.h>↵
↵
int main() {↵
int n, m_grams;↵
float mu = 1.2, G = 9.81, total_distance = 0.0, X = 0.0, Y = 0.0;↵
scanf("%d %d",&n,&m_grams);↵
float m = m_grams / 1000.0;↵
↵
for(int i = 0; i < n; i++) {↵
float I, x, y;↵
scanf("%f %f %f",&I,&x,&y);↵
float d = (I * I) / (2.0 * m * m * mu * G);↵
float norm = sqrt(x * x + y * y);↵
↵
float dx = d * (x / norm);↵
float dy = d * (y / norm);↵
↵
X += dx;↵
Y += dy;↵
↵
total_distance += d;↵
}↵
↵
printf("%.4f\n%.4f %.4f",total_distance,X,Y);↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
↵
[<h3 style="color:#4D87C7;">671145E. Hazlos primos II</h3>](https://mirror.codeforces.com/group/738Fi5tRsc/contest/671145/problem/E)↵
↵
<spoiler summary="Pista 1">↵
Calcula la distancia de cada número a su primo más cercano simulando las dos operaciones.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Ordena esas distancias.↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Primero debemos generar un arreglo del mismo tamaño que el arreglo original, es decir, tamaño $N$, llamemos a este arreglo <code>dist[N]</code>. Para cada elemento del arreglo original $a_i$, guardaremos en $dist_i$ la distancia a su primo más cercano. Vamos a dividir el número entre dos hasta llegar a cero, por cada división, vamos a revisar qué tan lejos está el número actual de un primo tanto hacia arriba como hacia abajo, mientras llevamos conteo del valor mínimo actual, es decir, si la división actual + su distancia al primo más cercano es menor que el valor que tenemos actualmente, lo actualizamos.↵
↵
Una vez que tengamos todas las distancias calculadas vamos a ordenarlas con cualquier algoritmo de ordenamiento (que no sea Bogo Sort ;D) y nuestra respuesta será ir iterando en orden este nuevo arreglo, restándole la distancia actual a nuestra $K$, que es las operaciones que tenemos disponibles.↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<stdbool.h>↵
↵
#define and &&↵
#define MAX_VAL 1050 ↵
#define ll long long↵
#define INF 200000000↵
↵
int min(int a, int b){↵
return a < b ? a : b;↵
}↵
↵
void bubbleSort(int n, int *arr){↵
for(int i=0; i<n-1; i++){↵
for(int j=0; j<n-i-1; j++){↵
if(arr[j] > arr[j+1]){↵
int tmp = arr[j];↵
arr[j] = arr[j+1];↵
arr[j+1] = tmp;↵
}↵
}↵
}↵
}↵
↵
bool isPrime(ll n){↵
if(n==1) return false;↵
if(n==2) return true;↵
if(n%2 == 0) return false;↵
↵
for(int i=3; i<n; i+=2){↵
if(n%i == 0) return false;↵
}↵
↵
return true;↵
}↵
↵
int distToPrime(int n){↵
if (isPrime(n)) return 0;↵
↵
int dist = 1;↵
while(true){↵
if (n - dist >= 2 && isPrime(n - dist)) return dist;↵
if (isPrime(n + dist)) return dist;↵
dist++;↵
}↵
}↵
↵
int distance(int n){↵
int min_cost = INF;↵
int divisions = 0;↵
while (n > 0) {↵
int cost = divisions + distToPrime(n);↵
min_cost = min(min_cost, cost);↵
↵
n /= 2;↵
divisions++;↵
}↵
↵
int zero = divisions + 2; ↵
min_cost = min(min_cost, zero);↵
↵
return min_cost;↵
}↵
↵
void solve(){↵
int n, k; ↵
scanf("%d %d", &n, &k);↵
↵
int board[n], costs[n];↵
for(int i=0; i<n; i++){↵
scanf("%d", &board[i]);↵
costs[i] = distance(board[i]);↵
}↵
↵
↵
bubbleSort(n, costs);↵
↵
↵
↵
int numPrimes = 0;↵
for(int i=0; i<n; i++){↵
if(costs[i] <= k){↵
numPrimes++;↵
k -= costs[i];↵
}else{↵
break;↵
}↵
}↵
↵
printf("%d\n", numPrimes);↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solución esperada">↵
En programación competitiva no es usual que una solución así funcione, debido a que estamos probando por fuerza bruta muchas posibles distancias, así como checar uno por uno los números primos y como cereza en el pastel, estamos usando un ordenamiento burbuja, que no es un algoritmo eficiente para ordenar. Hay muchos temas involucrados para lograr una solución eficiente para este problema. Sin embargo, describiremos la solución que nosotros esperábamos para este problema y dejamos como ejercicio para el lector la lectura sobre estos temas.↵
↵
En el caso de que los límites del problema fueran $1 \leq N,M,a_i, \leq 10^5$, la solución necesaria sería en cuanto a idea la misma, pero usaremos métodos distintos para lograrlo.↵
↵
Primero, necesitamos precomputar todos los primos hasta el elemento más grande del arreglo. Para esto se utiliza un algoritmo llamado [Criba de Eratóstenes](https://cp-algorithms-es.github.io/algebra/primos/criba-de-eratostenes.html), que nos devolverá una tabla que nos dirá si el i-ésimo número de la tabla es primo. Con el fin de consultar de forma rápida si cualquier número es primo mediante consultar la tabla.↵
↵
Con esto podremos probar las distancias a los primos de forma rápida. Para ordenar, hay múltiples algoritmos eficientes que nos permiten [ordenar](https://aprende.olimpiada-informatica.org/algoritmia-introduccion-4-coste-ordenar). En la solución del ejemplo se usa el ordenamiento por conteo (Counting Sort).↵
</spoiler>↵
↵
<spoiler summary="Código en C (solución esperada)">↵
Shoutout a [user:AlexJzG,2026-02-19] por la solución.↵
↵
~~~~~↵
#include <stdio.h>↵
↵
#define MAX 2002↵
↵
int sieve[MAX], nums[MAX], min_dist[MAX], sorted_dist[MAX];↵
↵
void get_primes() {↵
sieve[0] = sieve[1] = 1;↵
for (int i = 2; i < MAX; i++) {↵
if (sieve[i]) {↵
continue;↵
}↵
for (int j = i * 2; j < MAX; j += i) {↵
sieve[j] = 1;↵
}↵
}↵
}↵
↵
void get_min_dist() {↵
int last_prime = MAX + 100;↵
for (int i = MAX - 1; i >= 0; i--) {↵
if (sieve[i] == 0) {↵
last_prime = i;↵
}↵
if (min_dist[i] == 0) {↵
min_dist[i] = last_prime - i;↵
} else if (last_prime - i < min_dist[i]) {↵
min_dist[i] = last_prime - i;↵
}↵
}↵
last_prime = -100;↵
for (int i = 0; i < MAX; i++) {↵
if (sieve[i] == 0) {↵
last_prime = i;↵
}↵
↵
if (min_dist[i] == 0) {↵
min_dist[i] = i - last_prime;↵
} else if (i - last_prime < min_dist[i]) {↵
min_dist[i] = i - last_prime;↵
}↵
↵
if(min_dist[i/2] + 1 < min_dist[i]){↵
min_dist[i] = min_dist[i/2] + 1;↵
}↵
}↵
}↵
↵
void init() {↵
// Get primes (sieve[i] = 0 is prime)↵
get_primes();↵
↵
// Get min distance to p rimes↵
get_min_dist();↵
}↵
↵
void counting_sort() {↵
for (int i = 0; i < MAX; i++) {↵
sorted_dist[min_dist[i]] += nums[i];↵
}↵
}↵
↵
int max_primes(int m) {↵
int ans = 0;↵
for (int i = 0; i < MAX; i++) {↵
while (m >= i && sorted_dist[i] > 0) {↵
ans++;↵
m -= i;↵
sorted_dist[i]--;↵
}↵
}↵
return ans;↵
}↵
↵
int main() {↵
init();↵
int n, m, a;↵
scanf("%d %d\n", &n, &m);↵
for (int i = 0; i < n; i++) {↵
scanf("%d", &a);↵
nums[a]++;↵
}↵
counting_sort();↵
printf("%d\n", max_primes(m));↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
