¡Hola chicos! Muchas gracias por participar. Esta es la primera ocasión en la que el Club de Programación Competitiva de la Facultad de Ingeniería (CPCFI) escribe problemas originales para un concurso, y nos hizo muchísima ilusión que los resolvieran.↵
↵
Para quienes tengan 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 de 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:GusTimeTraveler,2026-02-17] con quien trabajé en partes iguales para la creación de problemas como miembro académico y problemsetter oficial del 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-20], [user:AlexJzG,2026-02-20], [user:lamocha,2026-02-20], [user:Nitter,2026-02-20], [user:salazarislas.daniel,2026-02-20], [user:Warddd,2026-02-20],[user:AldoEZ_21,2026-02-20], [user:zum,2026-02-20], [user:eve181836,2026-02-20].↵
↵
[<h3 style="color:#4D87C7;">671143A. Piedra, papel o tijera</h3>](https://codeforces.me/gym/671143/problem/A)↵
↵
El problema es uno clásico de implementación.↵
↵
La idea general se puede resumir en verificar quién fue la ganadora de cada ronda y llevar la cuenta de cuántas veces ganó cada quién en la totalidad del enfrentamiento. Finalmente, la información del output solicitado se resume a un condicional con los contadores que se hayan manejado.↵
↵
Para hacer ésto, hay un par de alternativas.↵
↵
La forma más obvia de hacerlo es leyendo las dos cadenas y acomodar condicionales hasta descifrar la conclusión que nos interesa: Eve gana, Ale gana o empataron.↵
Llevando la cuenta de cuántas veces ganó cada quién, es muy fácil decidir al final quién ganó todas las rondas (el contador que sea mayor), que es lo que se pide como salida.↵
↵
El siguiente código es una solución válida para el problema haciendo exactamente lo descrito.↵
↵
<spoiler summary="Solución en Java">↵
<pre><code>↵
import java.util.Scanner;↵
↵
public class Piedra_papel_o_tijeras {↵
public static void main(String[] args) {↵
Scanner input = new Scanner(System.in);↵
String piedra = "Piedra", papel = "Papel", tijeras = "Tijeras";↵
String[] jugadas;↵
int eveWins = 0, aleWins = 0, nRounds;↵
↵
nRounds = input.nextInt();↵
input.nextLine();↵
↵
for(int i = 0; i < nRounds; i++){↵
↵
jugadas = ( input.nextLine() ).split("\\s+");↵
↵
if( jugadas[0].equals(piedra) )↵
{↵
if( jugadas[1].equals(tijeras) )↵
eveWins++;↵
else if( jugadas[1].equals(papel) )↵
aleWins++;↵
else;↵
}↵
else if( jugadas[0].equals(papel) )↵
{↵
if( jugadas[1].equals(piedra) )↵
eveWins++;↵
else if( jugadas[1].equals(tijeras) )↵
aleWins++;↵
else;↵
}↵
else // Eve tiro tijeras↵
{↵
if( jugadas[1].equals(papel) )↵
eveWins++;↵
else if( jugadas[1].equals(piedra) )↵
aleWins++;↵
else;↵
}↵
}↵
↵
if( eveWins == aleWins )↵
System.out.println("Empate");↵
else if( eveWins > aleWins )↵
System.out.println("Eve");↵
else↵
System.out.println("Ale");↵
}↵
}↵
</code></pre>↵
</spoiler>↵
↵
Esta implementación se puede simplificar un poco si se ve de cierta forma. Pues no es necesario evaluar toda la cadena si se puede hacer con un caracter simbólico. Para el caso, se puede notar que las palabras 'Piedra', 'Papel' y 'Tijeras' difieren las tres en el tercer carácter, evitando tener que comparar toda la cadena, cosa que en lenguaje C puede ser especialmente útil. Entonces es posible checar únicamente ese carácter y simplificando los condicionales a algo equivalente obtenemos la siguiente solución válida también.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include <stdio.h>↵
#include <string.h>↵
#define SZ 10↵
↵
int main()↵
{↵
int eveWins = 0, aleWins = 0, nRounds;↵
char eveAns[SZ], aleAns[SZ];↵
↵
scanf("%d",&nRounds);↵
while(getchar() != '\n');↵
↵
for(int i = 0; i < nRounds; i++)↵
{↵
scanf("%s", eveAns);↵
scanf("%s", aleAns);↵
↵
if(eveAns[2] == 'e' && aleAns[2] == 'p') aleWins++;↵
if(eveAns[2] == 'p' && aleAns[2] == 'e') eveWins++;↵
if(eveAns[2] == 'j' && aleAns[2] == 'p') eveWins++;↵
if(eveAns[2] == 'p' && aleAns[2] == 'j') aleWins++;↵
if(eveAns[2] == 'j' && aleAns[2] == 'e') aleWins++;↵
if(eveAns[2] == 'e' && aleAns[2] == 'j') eveWins++;↵
}↵
↵
if( eveWins == aleWins )↵
printf("Empate\n");↵
else if( eveWins > aleWins )↵
printf("Eve\n");↵
else↵
printf("Ale\n");↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
Finalmente, se puede hacer la misma lógica con un único contador. Si en cada comparación sumas '+1' si Eve gana, y restas '-1' si Ale gana, el resultado final está en ver el signo del contador. Algo así es lo que se hace en la siguiente solución.↵
↵
<spoiler summary="Solución en Python">↵
<pre><code>↵
n = int(input())↵
cnt = 0↵
for i in range (n):↵
a,b = input().split(' ')↵
if(a==b):↵
continue↵
if(a == 'Tijeras'):↵
cnt += 1 if b == 'Papel' else -1↵
elif(a == 'Papel'):↵
cnt += 1 if b == 'Piedra' else -1↵
else:↵
cnt += 1 if b == 'Tijeras' else -1↵
↵
if cnt == 0:↵
print("Empate")↵
elif cnt<0:↵
print("Ale")↵
else:↵
print("Eve")↵
</code></pre>↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143B. Entrenamiento de equipo I</h3>](https://codeforces.me/gym/671143/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, 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 haciendo un *prefix sum* con los arreglos.↵
↵
La **complejidad final** alcanzable es $O(N)$, como se puede ver en las siguientes soluciones.↵
↵
<spoiler summary="Solución en C (Prefix Sum)">↵
<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;↵
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;↵
}↵
if( arns[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("2 ");↵
printed = true;↵
}↵
}↵
if( leon[i] == elMayor )↵
{↵
if( ! printed )↵
printf("3 ");↵
}↵
}↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
<spoiler summary="Solución en Java (Suma In Situ)">↵
<pre><code>↵
import java.util.Scanner;↵
import java.util.Math:↵
↵
public class Entrenamiento_de_equipo_I {↵
public static void main(String[] args) {↵
Scanner input = new Scanner(System.in);↵
int n, mayor;↵
long m = 0, a = 0, l = 0;↵
boolean printed = false;↵
n = input.nextInt();↵
int mikel[n], arns[n], leon[n];↵
↵
for(int i = 0; i < n; i++) mikel[i] = input.nextInt();↵
for(int i = 0; i < n; i++) arns[i] = input.nextInt();↵
for(int i = 0; i < n; i++) leon[i] = input.nextInt();↵
↵
for(int i = 0; i < n; i++) {↵
m += mikel[i];↵
a += arns[i];↵
l += leon[i];↵
mayor = Math.max(m, Math.max(a,l));↵
↵
if( m == mayor ) {↵
System.out.print("1 ");↵
printed = true;↵
}↵
else if( a == mayor && !printed ) {↵
System.out.print("2 ");↵
printed = true;↵
}↵
else {↵
System.out.print("3 ");↵
}↵
}↵
return 0;↵
}↵
}↵
</code></pre>↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143C. Acomodo cuadrático</h3>](https://codeforces.me/gym/671143/problem/C)↵
↵
<spoiler summary="Pista 1">↵
Usa tres ciclos <code>for</code> anidados.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Para cada combinación, checa si las raíces de esa combinación de coeficientes es igual a las raíces que te da David↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Usa un triple <code>for</code> para probar todas las combinaciones de coeficientes $a,b,c$, obtén las raíces de cada ecuación que formen los coeficientes con la fórmula de Bhaskara (AKA "La chicharronera"): $\frac{-b\pm \sqrt{b^2 - 4ac}}{2a}$. Esto siempre y cuando compruebes que la ecuación no genera números complejos, esto mediante evaluar la desigualdad del discriminante $b^2 >= 4ac$↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<stdbool.h>↵
#include<math.h>↵
↵
#define EPS 1e-6↵
↵
typedef struct{↵
float x1,x2;↵
}Roots;↵
↵
bool isComplex(int a, int b, int c){↵
return b*b - 4*a*c < 0; ↵
}↵
↵
Roots bhaskara(int a, int b, int c){↵
Roots answer;↵
float discriminant = b*b - 4*a*c;↵
answer.x1 = (-b+sqrt(discriminant))/(2*a);↵
answer.x2 = (-b-sqrt(discriminant))/(2*a);↵
return answer;↵
}↵
↵
void solve(){↵
int n,x1,x2; scanf("%d %d %d",&n, &x1, &x2);↵
int as[n], bs[n], cs[n];↵
for(int i=0; i<n; i++){↵
scanf("%d %d %d", &as[i],&bs[i],&cs[i]);↵
}↵
↵
for(int i=0; i<n; i++){↵
for(int j=0; j<n; j++){↵
for(int k=0; k<n; k++){↵
if(!isComplex(as[i],bs[j],cs[k])){↵
Roots tmp = bhaskara(as[i], bs[j], cs[k]);↵
bool match_direct = (fabs(tmp.x1 - x1) < EPS && fabs(tmp.x2 - x2) < EPS);↵
bool match_swapped = (fabs(tmp.x1 - x2) < EPS && fabs(tmp.x2 - x1) < EPS);↵
↵
if (match_direct || match_swapped) {↵
printf("%d %d %d\n", as[i], bs[j], cs[k]);↵
return;↵
}↵
}↵
}↵
}↵
}↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Código en Python">↵
~~~~~↵
import math↵
↵
EPS = 1e-9↵
↵
def isComplex(a: int, b: int, c: int) -> bool:↵
return b*b — 4*a*c < 0↵
↵
def bhaskara(a: int, b: int, c:int):↵
return (-b+math.sqrt(b*b — 4*a*c))/(2*a), (-b-math.sqrt(b*b — 4*a*c))/(2*a)↵
↵
n,x1,x2 = [int(x) for x in input().split()]↵
↵
a_s = []↵
b_s = []↵
c_s = []↵
↵
for _ in range(n):↵
a,b,c = [int(x) for x in input().split()]↵
a_s.append(a)↵
b_s.append(b)↵
c_s.append(c)↵
↵
for i in range(n):↵
for j in range(n):↵
for k in range(n):↵
if(not isComplex(a_s[i],b_s[j],c_s[k])):↵
tx1, tx2 = bhaskara(a_s[i],b_s[j],c_s[k])↵
match_direct = abs(tx1 — x1) < EPS and abs(tx2 — x2) < EPS↵
match_swapped = abs(tx1 — x2) < EPS and abs(tx2 — x1) < EPS↵
↵
if match_direct or match_swapped:↵
print(f'{a_s[i]} {b_s[j]} {c_s[k]}') ↵
exit()↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Otra solución más eficiente">↵
Las [formulas de Vieta](https://en.wikipedia.org/wiki/Vieta%27s_formulas) nos permiten establecer una relación entre raíces y coeficientes. En concreto, para una ecuación de segundo grado tenemos las siguientes fórmulas.↵
↵
**Suma de las raíces**↵
$$x_1 + x_2 = -\frac{b}{a}$$↵
$$b = -a(x_1 + x_2)$$↵
↵
**Producto de las raíces**↵
$$x_1 \cdot x_2 = \frac{c}{a}$$↵
$$c = a(x_1 \cdot x_2)$$↵
↵
Con esto, tenemos dos ecuaciones que dependen de $a$, por lo tanto, ahora solo necesitamos comprobar para cada $a$ si existe una $b$ y una $c$ que cumplan las dos ecuaciones.↵
↵
Para hacer esto de forma eficiente podemos guardar todas las $b$ y $c$ en dos [sets](https://www.w3schools.com/python/python_sets.asp) y buscar los valores en sustituyendo los valores de las raíces y de cada $a$ en ambas ecuaciones. ↵
</spoiler>↵
↵
<spoiler summary="Código en Python (Vieta)">↵
~~~~~↵
def sumOfRoots(a: int, x1: int, x2:int) -> int:↵
return -a*(x1+x2)↵
↵
def productOfRoots(a: int, x1:int, x2:int) -> int:↵
return a*(x1*x2)↵
↵
n,x1,x2 = [int(x) for x in input().split()]↵
↵
a_s = []↵
b_s = set()↵
c_s = set()↵
for _ in range(n):↵
a,b,c = [int(x) for x in input().split()]↵
a_s.append(a)↵
b_s.add(b)↵
c_s.add(c)↵
↵
for a in a_s:↵
b = sumOfRoots(a,x1,x2)↵
c = productOfRoots(a,x1,x2)↵
if b in b_s and c in c_s:↵
print(f'{a} {b} {c}')↵
exit()↵
↵
~~~~~↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143D. El billar no es de vagos II</h3>](https://codeforces.me/gym/671143/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;">671143E. Hazlos primos I</h3>](https://codeforces.me/gym/671143/problem/E)↵
↵
<spoiler summary="Pista 1">↵
Calcula la distancia de cada número a su primo más cercano simulando la operación hacia arriba con la suma y hacia abajo con la resta↵
</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. Esto, mediante calcular ambos casos.↵
<ul>↵
<li>¿Qué pasa si sumamos hasta llegar al siguiente primo?</li>↵
<li>¿Qué pasa si restamos hasta llegar al siguiente primo?</li>↵
</ul>↵
↵
Nos quedaremos con el mínimo de ambos.↵
↵
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 ↵
↵
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;↵
}↵
}↵
}↵
}↵
↵
void primes(int max_limit, bool *isPrime){↵
for(int i=0; i<max_limit; i++){↵
isPrime[i] = true;↵
}↵
↵
isPrime[0] = false;↵
isPrime[1] = false;↵
↵
for(int i=2; i<max_limit; i++){↵
for(int j=2; j<i; j++){↵
if(i % j == 0){↵
isPrime[i] = false;↵
break;↵
}↵
}↵
}↵
}↵
↵
void solve(){↵
int n, k; ↵
scanf("%d %d", &n, &k);↵
↵
int board[n];↵
for(int i=0; i<n; i++){↵
scanf("%d", &board[i]);↵
}↵
↵
bool isPrime[MAX_VAL];↵
↵
primes(MAX_VAL, isPrime);↵
↵
int primeDist[n];↵
↵
for(int i=0; i<n; i++){↵
int lower = board[i];↵
while(lower >= 0 and isPrime[lower] == false){↵
lower--;↵
}↵
↵
int upper = board[i];↵
while(upper < MAX_VAL and isPrime[upper] == false){↵
upper++;↵
}↵
↵
int distDown = (lower >= 0) ? (board[i] - lower) : 10000;↵
int distUp = (upper < MAX_VAL) ? (upper - board[i]) : 10000;↵
↵
primeDist[i] = min(distDown, distUp);↵
}↵
↵
bubbleSort(n, primeDist);↵
↵
int numPrimes = 0;↵
for(int i=0; i<n; i++){↵
if(primeDist[i] <= k){↵
numPrimes++;↵
k -= primeDist[i];↵
}↵
}↵
↵
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 en C del ejemplo se usa el ordenamiento por conteo (Counting Sort) y en la solución en Java del ejemplo se utiliza <code>Collections.sort()</code> y el cálculo de distancias se hace mediante [búsqueda binaria](https://zums-stuff.github.io/CPCFI-Webpage/binary-search/busqueda-binaria/).↵
</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 = -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;↵
}↵
}↵
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;↵
}↵
}↵
}↵
↵
void init() {↵
// Get primes (sieve[i] = 0 is prime)↵
get_primes();↵
↵
// Get min distance to primes↵
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>↵
↵
<spoiler summary="Código en Java (solución esperada)">↵
Shoutout a [user:salazarislas.daniel,2026-02-19] por la solución.↵
↵
~~~~~↵
import java.util.*;↵
↵
public class B_Hazlos_primos_I {↵
↵
public static ArrayList<Integer> sieve(int n) {↵
boolean[] isPrime = new boolean[n + 1];↵
Arrays.fill(isPrime, true);↵
if (n >= 0) isPrime[0] = false;↵
if (n >= 1) isPrime[1] = false;↵
for (int i = 2; i * i <= n; i++) {↵
if (isPrime[i]) {↵
for (int j = i * i; j <= n; j += i) {↵
isPrime[j] = false;↵
}↵
}↵
}↵
ArrayList<Integer> primes = new ArrayList<>();↵
for (int i = 2; i <= n; i++) {↵
if (isPrime[i]) {↵
primes.add(i);↵
}↵
}↵
return primes;↵
}↵
public static void main(String[] args) {↵
Scanner sc = new Scanner(System.in);↵
int n, m;↵
n = sc.nextInt();↵
m = sc.nextInt();↵
int[] arr = new int[n];↵
int maxi=0;↵
for (int i = 0; i < n; i++) {↵
arr[i] = sc.nextInt();↵
maxi=Math.max(maxi,arr[i]);↵
}↵
// Generar todos los primos hasta m↵
ArrayList<Integer> primes = sieve(2*maxi);↵
// Crear array para diferencias↵
ArrayList<Integer> diffs = new ArrayList<>();↵
for (int i = 0; i < n; i++) {↵
int x = arr[i];↵
// Buscar lower bound (primo >= x)↵
int left = 0, right = primes.size();↵
while (left < right) {↵
int mid = left + (right - left) / 2;↵
if (primes.get(mid) < x) {↵
left = mid + 1;↵
} else {↵
right = mid;↵
}↵
}↵
int upperIdx = left;↵
int lowerIdx = left - 1;↵
int diff = Integer.MAX_VALUE;↵
if (upperIdx < primes.size() && primes.get(upperIdx) == x) {↵
diff = 0;↵
} else {↵
int upperDiff = (upperIdx < primes.size()) ? Math.abs(primes.get(upperIdx) - x) : Integer.MAX_VALUE;↵
int lowerDiff = (lowerIdx >= 0) ? Math.abs(x - primes.get(lowerIdx)) : Integer.MAX_VALUE;↵
diff = Math.min(upperDiff, lowerDiff);↵
}↵
diffs.add(diff);↵
}↵
// for(int d:diffs){↵
// System.out.print(d+" ");↵
// }↵
// System.out.println("");↵
// Ordenar el vector de diferencias↵
Collections.sort(diffs);↵
// Imprimir diferencias ordenadas↵
int res=0;↵
for(int d:diffs){↵
if(m>=d){↵
res++;↵
m-=d;↵
}↵
else{↵
break;↵
}↵
}↵
System.out.println(res);↵
sc.close();↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
Para quienes tengan 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 de 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:GusTimeTraveler,2026-02-17] con quien trabajé en partes iguales para la creación de problemas como miembro académico y problemsetter oficial del 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-20], [user:AlexJzG,2026-02-20], [user:lamocha,2026-02-20], [user:Nitter,2026-02-20], [user:salazarislas.daniel,2026-02-20], [user:Warddd,2026-02-20],[user:AldoEZ_21,2026-02-20], [user:zum,2026-02-20], [user:eve181836,2026-02-20].↵
↵
[<h3 style="color:#4D87C7;">671143A. Piedra, papel o tijera</h3>](https://codeforces.me/gym/671143/problem/A)↵
↵
El problema es uno clásico de implementación.↵
↵
La idea general se puede resumir en verificar quién fue la ganadora de cada ronda y llevar la cuenta de cuántas veces ganó cada quién en la totalidad del enfrentamiento. Finalmente, la información del output solicitado se resume a un condicional con los contadores que se hayan manejado.↵
↵
Para hacer ésto, hay un par de alternativas.↵
↵
La forma más obvia de hacerlo es leyendo las dos cadenas y acomodar condicionales hasta descifrar la conclusión que nos interesa: Eve gana, Ale gana o empataron.↵
Llevando la cuenta de cuántas veces ganó cada quién, es muy fácil decidir al final quién ganó todas las rondas (el contador que sea mayor), que es lo que se pide como salida.↵
↵
El siguiente código es una solución válida para el problema haciendo exactamente lo descrito.↵
↵
<spoiler summary="Solución en Java">↵
<pre><code>↵
import java.util.Scanner;↵
↵
public class Piedra_papel_o_tijeras {↵
public static void main(String[] args) {↵
Scanner input = new Scanner(System.in);↵
String piedra = "Piedra", papel = "Papel", tijeras = "Tijeras";↵
String[] jugadas;↵
int eveWins = 0, aleWins = 0, nRounds;↵
↵
nRounds = input.nextInt();↵
input.nextLine();↵
↵
for(int i = 0; i < nRounds; i++){↵
↵
jugadas = ( input.nextLine() ).split("\\s+");↵
↵
if( jugadas[0].equals(piedra) )↵
{↵
if( jugadas[1].equals(tijeras) )↵
eveWins++;↵
else if( jugadas[1].equals(papel) )↵
aleWins++;↵
else;↵
}↵
else if( jugadas[0].equals(papel) )↵
{↵
if( jugadas[1].equals(piedra) )↵
eveWins++;↵
else if( jugadas[1].equals(tijeras) )↵
aleWins++;↵
else;↵
}↵
else // Eve tiro tijeras↵
{↵
if( jugadas[1].equals(papel) )↵
eveWins++;↵
else if( jugadas[1].equals(piedra) )↵
aleWins++;↵
else;↵
}↵
}↵
↵
if( eveWins == aleWins )↵
System.out.println("Empate");↵
else if( eveWins > aleWins )↵
System.out.println("Eve");↵
else↵
System.out.println("Ale");↵
}↵
}↵
</code></pre>↵
</spoiler>↵
↵
Esta implementación se puede simplificar un poco si se ve de cierta forma. Pues no es necesario evaluar toda la cadena si se puede hacer con un caracter simbólico. Para el caso, se puede notar que las palabras 'Piedra', 'Papel' y 'Tijeras' difieren las tres en el tercer carácter, evitando tener que comparar toda la cadena, cosa que en lenguaje C puede ser especialmente útil. Entonces es posible checar únicamente ese carácter y simplificando los condicionales a algo equivalente obtenemos la siguiente solución válida también.↵
↵
<spoiler summary="Solución en C">↵
<pre><code>↵
#include <stdio.h>↵
#include <string.h>↵
#define SZ 10↵
↵
int main()↵
{↵
int eveWins = 0, aleWins = 0, nRounds;↵
char eveAns[SZ], aleAns[SZ];↵
↵
scanf("%d",&nRounds);↵
while(getchar() != '\n');↵
↵
for(int i = 0; i < nRounds; i++)↵
{↵
scanf("%s", eveAns);↵
scanf("%s", aleAns);↵
↵
if(eveAns[2] == 'e' && aleAns[2] == 'p') aleWins++;↵
if(eveAns[2] == 'p' && aleAns[2] == 'e') eveWins++;↵
if(eveAns[2] == 'j' && aleAns[2] == 'p') eveWins++;↵
if(eveAns[2] == 'p' && aleAns[2] == 'j') aleWins++;↵
if(eveAns[2] == 'j' && aleAns[2] == 'e') aleWins++;↵
if(eveAns[2] == 'e' && aleAns[2] == 'j') eveWins++;↵
}↵
↵
if( eveWins == aleWins )↵
printf("Empate\n");↵
else if( eveWins > aleWins )↵
printf("Eve\n");↵
else↵
printf("Ale\n");↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
Finalmente, se puede hacer la misma lógica con un único contador. Si en cada comparación sumas '+1' si Eve gana, y restas '-1' si Ale gana, el resultado final está en ver el signo del contador. Algo así es lo que se hace en la siguiente solución.↵
↵
<spoiler summary="Solución en Python">↵
<pre><code>↵
n = int(input())↵
cnt = 0↵
for i in range (n):↵
a,b = input().split(' ')↵
if(a==b):↵
continue↵
if(a == 'Tijeras'):↵
cnt += 1 if b == 'Papel' else -1↵
elif(a == 'Papel'):↵
cnt += 1 if b == 'Piedra' else -1↵
else:↵
cnt += 1 if b == 'Tijeras' else -1↵
↵
if cnt == 0:↵
print("Empate")↵
elif cnt<0:↵
print("Ale")↵
else:↵
print("Eve")↵
</code></pre>↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143B. Entrenamiento de equipo I</h3>](https://codeforces.me/gym/671143/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, 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 haciendo un *prefix sum* con los arreglos.↵
↵
La **complejidad final** alcanzable es $O(N)$, como se puede ver en las siguientes soluciones.↵
↵
<spoiler summary="Solución en C (Prefix Sum)">↵
<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;↵
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;↵
}↵
if( arns[i] == elMayor )↵
{↵
if( ! printed )↵
{↵
printf("2 ");↵
printed = true;↵
}↵
}↵
if( leon[i] == elMayor )↵
{↵
if( ! printed )↵
printf("3 ");↵
}↵
}↵
↵
return 0;↵
}↵
</code></pre>↵
</spoiler>↵
↵
<spoiler summary="Solución en Java (Suma In Situ)">↵
<pre><code>↵
import java.util.Scanner;↵
import java.util.Math:↵
↵
public class Entrenamiento_de_equipo_I {↵
public static void main(String[] args) {↵
Scanner input = new Scanner(System.in);↵
int n, mayor;↵
long m = 0, a = 0, l = 0;↵
boolean printed = false;↵
n = input.nextInt();↵
int mikel[n], arns[n], leon[n];↵
↵
for(int i = 0; i < n; i++) mikel[i] = input.nextInt();↵
for(int i = 0; i < n; i++) arns[i] = input.nextInt();↵
for(int i = 0; i < n; i++) leon[i] = input.nextInt();↵
↵
for(int i = 0; i < n; i++) {↵
m += mikel[i];↵
a += arns[i];↵
l += leon[i];↵
mayor = Math.max(m, Math.max(a,l));↵
↵
if( m == mayor ) {↵
System.out.print("1 ");↵
printed = true;↵
}↵
else if( a == mayor && !printed ) {↵
System.out.print("2 ");↵
printed = true;↵
}↵
else {↵
System.out.print("3 ");↵
}↵
}↵
return 0;↵
}↵
}↵
</code></pre>↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143C. Acomodo cuadrático</h3>](https://codeforces.me/gym/671143/problem/C)↵
↵
<spoiler summary="Pista 1">↵
Usa tres ciclos <code>for</code> anidados.↵
</spoiler>↵
↵
<spoiler summary="Pista 2">↵
Para cada combinación, checa si las raíces de esa combinación de coeficientes es igual a las raíces que te da David↵
</spoiler>↵
↵
<spoiler summary="Solución">↵
Usa un triple <code>for</code> para probar todas las combinaciones de coeficientes $a,b,c$, obtén las raíces de cada ecuación que formen los coeficientes con la fórmula de Bhaskara (AKA "La chicharronera"): $\frac{-b\pm \sqrt{b^2 - 4ac}}{2a}$. Esto siempre y cuando compruebes que la ecuación no genera números complejos, esto mediante evaluar la desigualdad del discriminante $b^2 >= 4ac$↵
</spoiler>↵
↵
<spoiler summary="Código en C">↵
↵
~~~~~↵
#include<stdio.h>↵
#include<stdbool.h>↵
#include<math.h>↵
↵
#define EPS 1e-6↵
↵
typedef struct{↵
float x1,x2;↵
}Roots;↵
↵
bool isComplex(int a, int b, int c){↵
return b*b - 4*a*c < 0; ↵
}↵
↵
Roots bhaskara(int a, int b, int c){↵
Roots answer;↵
float discriminant = b*b - 4*a*c;↵
answer.x1 = (-b+sqrt(discriminant))/(2*a);↵
answer.x2 = (-b-sqrt(discriminant))/(2*a);↵
return answer;↵
}↵
↵
void solve(){↵
int n,x1,x2; scanf("%d %d %d",&n, &x1, &x2);↵
int as[n], bs[n], cs[n];↵
for(int i=0; i<n; i++){↵
scanf("%d %d %d", &as[i],&bs[i],&cs[i]);↵
}↵
↵
for(int i=0; i<n; i++){↵
for(int j=0; j<n; j++){↵
for(int k=0; k<n; k++){↵
if(!isComplex(as[i],bs[j],cs[k])){↵
Roots tmp = bhaskara(as[i], bs[j], cs[k]);↵
bool match_direct = (fabs(tmp.x1 - x1) < EPS && fabs(tmp.x2 - x2) < EPS);↵
bool match_swapped = (fabs(tmp.x1 - x2) < EPS && fabs(tmp.x2 - x1) < EPS);↵
↵
if (match_direct || match_swapped) {↵
printf("%d %d %d\n", as[i], bs[j], cs[k]);↵
return;↵
}↵
}↵
}↵
}↵
}↵
}↵
↵
int main(){↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Código en Python">↵
~~~~~↵
import math↵
↵
EPS = 1e-9↵
↵
def isComplex(a: int, b: int, c: int) -> bool:↵
return b*b — 4*a*c < 0↵
↵
def bhaskara(a: int, b: int, c:int):↵
return (-b+math.sqrt(b*b — 4*a*c))/(2*a), (-b-math.sqrt(b*b — 4*a*c))/(2*a)↵
↵
n,x1,x2 = [int(x) for x in input().split()]↵
↵
a_s = []↵
b_s = []↵
c_s = []↵
↵
for _ in range(n):↵
a,b,c = [int(x) for x in input().split()]↵
a_s.append(a)↵
b_s.append(b)↵
c_s.append(c)↵
↵
for i in range(n):↵
for j in range(n):↵
for k in range(n):↵
if(not isComplex(a_s[i],b_s[j],c_s[k])):↵
tx1, tx2 = bhaskara(a_s[i],b_s[j],c_s[k])↵
match_direct = abs(tx1 — x1) < EPS and abs(tx2 — x2) < EPS↵
match_swapped = abs(tx1 — x2) < EPS and abs(tx2 — x1) < EPS↵
↵
if match_direct or match_swapped:↵
print(f'{a_s[i]} {b_s[j]} {c_s[k]}') ↵
exit()↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="Otra solución más eficiente">↵
Las [formulas de Vieta](https://en.wikipedia.org/wiki/Vieta%27s_formulas) nos permiten establecer una relación entre raíces y coeficientes. En concreto, para una ecuación de segundo grado tenemos las siguientes fórmulas.↵
↵
**Suma de las raíces**↵
$$x_1 + x_2 = -\frac{b}{a}$$↵
$$b = -a(x_1 + x_2)$$↵
↵
**Producto de las raíces**↵
$$x_1 \cdot x_2 = \frac{c}{a}$$↵
$$c = a(x_1 \cdot x_2)$$↵
↵
Con esto, tenemos dos ecuaciones que dependen de $a$, por lo tanto, ahora solo necesitamos comprobar para cada $a$ si existe una $b$ y una $c$ que cumplan las dos ecuaciones.↵
↵
Para hacer esto de forma eficiente podemos guardar todas las $b$ y $c$ en dos [sets](https://www.w3schools.com/python/python_sets.asp) y buscar los valores en sustituyendo los valores de las raíces y de cada $a$ en ambas ecuaciones. ↵
</spoiler>↵
↵
<spoiler summary="Código en Python (Vieta)">↵
~~~~~↵
def sumOfRoots(a: int, x1: int, x2:int) -> int:↵
return -a*(x1+x2)↵
↵
def productOfRoots(a: int, x1:int, x2:int) -> int:↵
return a*(x1*x2)↵
↵
n,x1,x2 = [int(x) for x in input().split()]↵
↵
a_s = []↵
b_s = set()↵
c_s = set()↵
for _ in range(n):↵
a,b,c = [int(x) for x in input().split()]↵
a_s.append(a)↵
b_s.add(b)↵
c_s.add(c)↵
↵
for a in a_s:↵
b = sumOfRoots(a,x1,x2)↵
c = productOfRoots(a,x1,x2)↵
if b in b_s and c in c_s:↵
print(f'{a} {b} {c}')↵
exit()↵
↵
~~~~~↵
</spoiler>↵
↵
[<h3 style="color:#4D87C7;">671143D. El billar no es de vagos II</h3>](https://codeforces.me/gym/671143/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;">671143E. Hazlos primos I</h3>](https://codeforces.me/gym/671143/problem/E)↵
↵
<spoiler summary="Pista 1">↵
Calcula la distancia de cada número a su primo más cercano simulando la operación hacia arriba con la suma y hacia abajo con la resta↵
</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. Esto, mediante calcular ambos casos.↵
<ul>↵
<li>¿Qué pasa si sumamos hasta llegar al siguiente primo?</li>↵
<li>¿Qué pasa si restamos hasta llegar al siguiente primo?</li>↵
</ul>↵
↵
Nos quedaremos con el mínimo de ambos.↵
↵
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 ↵
↵
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;↵
}↵
}↵
}↵
}↵
↵
void primes(int max_limit, bool *isPrime){↵
for(int i=0; i<max_limit; i++){↵
isPrime[i] = true;↵
}↵
↵
isPrime[0] = false;↵
isPrime[1] = false;↵
↵
for(int i=2; i<max_limit; i++){↵
for(int j=2; j<i; j++){↵
if(i % j == 0){↵
isPrime[i] = false;↵
break;↵
}↵
}↵
}↵
}↵
↵
void solve(){↵
int n, k; ↵
scanf("%d %d", &n, &k);↵
↵
int board[n];↵
for(int i=0; i<n; i++){↵
scanf("%d", &board[i]);↵
}↵
↵
bool isPrime[MAX_VAL];↵
↵
primes(MAX_VAL, isPrime);↵
↵
int primeDist[n];↵
↵
for(int i=0; i<n; i++){↵
int lower = board[i];↵
while(lower >= 0 and isPrime[lower] == false){↵
lower--;↵
}↵
↵
int upper = board[i];↵
while(upper < MAX_VAL and isPrime[upper] == false){↵
upper++;↵
}↵
↵
int distDown = (lower >= 0) ? (board[i] - lower) : 10000;↵
int distUp = (upper < MAX_VAL) ? (upper - board[i]) : 10000;↵
↵
primeDist[i] = min(distDown, distUp);↵
}↵
↵
bubbleSort(n, primeDist);↵
↵
int numPrimes = 0;↵
for(int i=0; i<n; i++){↵
if(primeDist[i] <= k){↵
numPrimes++;↵
k -= primeDist[i];↵
}↵
}↵
↵
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 en C del ejemplo se usa el ordenamiento por conteo (Counting Sort) y en la solución en Java del ejemplo se utiliza <code>Collections.sort()</code> y el cálculo de distancias se hace mediante [búsqueda binaria](https://zums-stuff.github.io/CPCFI-Webpage/binary-search/busqueda-binaria/).↵
</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 = -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;↵
}↵
}↵
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;↵
}↵
}↵
}↵
↵
void init() {↵
// Get primes (sieve[i] = 0 is prime)↵
get_primes();↵
↵
// Get min distance to primes↵
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>↵
↵
<spoiler summary="Código en Java (solución esperada)">↵
Shoutout a [user:salazarislas.daniel,2026-02-19] por la solución.↵
↵
~~~~~↵
import java.util.*;↵
↵
public class B_Hazlos_primos_I {↵
↵
public static ArrayList<Integer> sieve(int n) {↵
boolean[] isPrime = new boolean[n + 1];↵
Arrays.fill(isPrime, true);↵
if (n >= 0) isPrime[0] = false;↵
if (n >= 1) isPrime[1] = false;↵
for (int i = 2; i * i <= n; i++) {↵
if (isPrime[i]) {↵
for (int j = i * i; j <= n; j += i) {↵
isPrime[j] = false;↵
}↵
}↵
}↵
ArrayList<Integer> primes = new ArrayList<>();↵
for (int i = 2; i <= n; i++) {↵
if (isPrime[i]) {↵
primes.add(i);↵
}↵
}↵
return primes;↵
}↵
public static void main(String[] args) {↵
Scanner sc = new Scanner(System.in);↵
int n, m;↵
n = sc.nextInt();↵
m = sc.nextInt();↵
int[] arr = new int[n];↵
int maxi=0;↵
for (int i = 0; i < n; i++) {↵
arr[i] = sc.nextInt();↵
maxi=Math.max(maxi,arr[i]);↵
}↵
// Generar todos los primos hasta m↵
ArrayList<Integer> primes = sieve(2*maxi);↵
// Crear array para diferencias↵
ArrayList<Integer> diffs = new ArrayList<>();↵
for (int i = 0; i < n; i++) {↵
int x = arr[i];↵
// Buscar lower bound (primo >= x)↵
int left = 0, right = primes.size();↵
while (left < right) {↵
int mid = left + (right - left) / 2;↵
if (primes.get(mid) < x) {↵
left = mid + 1;↵
} else {↵
right = mid;↵
}↵
}↵
int upperIdx = left;↵
int lowerIdx = left - 1;↵
int diff = Integer.MAX_VALUE;↵
if (upperIdx < primes.size() && primes.get(upperIdx) == x) {↵
diff = 0;↵
} else {↵
int upperDiff = (upperIdx < primes.size()) ? Math.abs(primes.get(upperIdx) - x) : Integer.MAX_VALUE;↵
int lowerDiff = (lowerIdx >= 0) ? Math.abs(x - primes.get(lowerIdx)) : Integer.MAX_VALUE;↵
diff = Math.min(upperDiff, lowerDiff);↵
}↵
diffs.add(diff);↵
}↵
// for(int d:diffs){↵
// System.out.print(d+" ");↵
// }↵
// System.out.println("");↵
// Ordenar el vector de diferencias↵
Collections.sort(diffs);↵
// Imprimir diferencias ordenadas↵
int res=0;↵
for(int d:diffs){↵
if(m>=d){↵
res++;↵
m-=d;↵
}↵
else{↵
break;↵
}↵
}↵
System.out.println(res);↵
sc.close();↵
}↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
