02 · La competencia y la estrategia
Aprender a programar · Ruta de Aprendizaje
Antes de empezar. Leer, compilar y ejecutar un programa: 01 - Tu primer programa.
🎯 Objetivos
Al terminar este módulo sabes:
- Leer un enunciado de competencia: entrada, salida, restricciones y subtareas.
- Usar las restricciones para decidir si tu idea alcanza en tiempo.
- Evitar el error clásico de desbordar un
int, y entender los veredictos del juez.
📖 La lección
Cómo es una competencia
En una olimpiada (OCI, IOI) recibes unos pocos problemas y varias horas. Cada problema vale 100 puntos repartidos en subtareas: versiones más fáciles del problema (con límites más chicos) que valen puntos parciales. Esto define la estrategia central de toda la ruta: asegurar subtareas vale más que perseguir la solución perfecta. Una solución sencilla puede obtener puntos si cumple las condiciones de alguna subtarea; la distribución depende del problema.
Un problema típico se ve así (los números cambian de problema en problema; la forma, no):
Si el diagrama no cabe, deslízalo horizontalmente.
Cada subtarea es, en la práctica, un problema distinto con su propio límite: la primera se gana con la idea más simple que exista, la última exige la solución eficiente. Por eso se leen todas antes de programar.
Anatomía de un enunciado
Un enunciado describe una situación, una tarea, la entrada, la salida y los límites. La historia puede contener condiciones esenciales: tradúcelas a operaciones, sin saltártelas.
Ejemplo: entradas para un festival. Se venden n entradas a p pesos cada una. Se pide el dinero recaudado.
| Parte | Qué dice | Qué deducimos |
|---|---|---|
| Entrada | dos enteros n y p | hay dos datos, no una lista de compradores |
| Restricciones | 0 ≤ n ≤ 10⁹, 1 ≤ p ≤ 10⁶ | repetir n veces puede ser demasiado trabajo |
| Tarea | calcular la recaudación | sumar p n veces o multiplicar n por p |
| Salida | un entero | con 3 2000, imprimir 6000 |
La suma repetida usa n operaciones; el producto hace una cantidad constante. Pero elegir la fórmula no resuelve el rango: el máximo es 10¹⁵, de modo que hay que multiplicar en long long. Rapidez y representación son dos decisiones distintas.
Las restricciones son tu brújula
Volvamos al festival. Con n = 3, sumar 2000 tres veces y multiplicar
3 * 2000 dan 6000. Con n = 10⁹, la primera idea exige mil millones
de sumas; la segunda sigue haciendo una multiplicación. Esa comparación ya
permite elegir sin conocer todavía una notación matemática especial.
No confundas el valor de n con la cantidad de datos de entrada. El festival entrega solo dos números. Si otro problema entrega una lista de n precios, incluso una buena solución necesita leer sus n valores.
Por ahora haz dos preguntas: ¿cuántas veces se repite el trabajo?, ¿cuánto puede valer el resultado? En el módulo 07 contaremos ciclos y aprenderemos a resumir su crecimiento. Una tabla de tamaños no reemplaza ese razonamiento ni garantiza un tiempo de ejecución.
El template y la lectura de varios casos
Muchos problemas traen t casos de prueba en una sola ejecución:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t; // número de casos de prueba
while (t--) { // repite t veces (t-- resta 1 en cada vuelta)
long long n;
cin >> n;
cout << (n % 2 == 0 ? "PAR" : "IMPAR") << "\n";
}
return 0;
}Las dos líneas de sync_with_stdio/cin.tie aceleran la lectura — inclúyelas
siempre; en entradas grandes marcan la diferencia entre pasar y TLE. El
while (t--) es la forma corta de “repetir t veces”: la condición usa el
valor de t y de paso le resta 1, hasta que llega a 0.
El enemigo silencioso: overflow
Un int aguanta hasta ~2·10⁹. Multiplica dos números de un millón y…
int chico = 1000000;
long long malo = chico * chico; // ¡se desborda ANTES de guardarse!
long long bueno = 1000000LL * 1000000LL; // la LL fuerza aritmética de 64 bits
cout << malo << "\n" << bueno << "\n";La primera multiplicación se desborda con int de 32 bits: en C++ el
desbordamiento de enteros con signo tiene comportamiento indefinido, así
que no hay una salida garantizada. Guardar después en long long no lo
repara: la multiplicación ya ocurrió entre ints. La segunda expresión
sí se calcula en 64 bits y vale 1000000000000.
El dibujo muestra el rango representable. No asigna un resultado a una operación que desborda.
Si el diagrama no cabe, deslízalo horizontalmente.
Regla práctica de competencia: si los valores pueden superar 10⁹, trabaja en
long long de punta a punta. Y el reflejo que salva partidas: cuando un
resultado que debería ser positivo aparece negativo o absurdamente chico, la
primera sospecha es overflow.
Los veredictos del juez
AC aceptado · WA respuesta incorrecta · TLE se pasó del tiempo · RTE el programa se cayó (índice fuera de rango, división por cero) · CE no compiló. Son pistas, no diagnósticos exclusivos: un acceso inválido también puede causar WA, y un ciclo infinito puede causar TLE. Como punto de partida, mira WA → lógica o caso borde; TLE → complejidad; RTE → índices y límites.
Del enunciado a una solución
- Lee la tarea y las restricciones (¿qué n? ¿qué cabe?).
- Piensa un ejemplo chico a mano antes de programar.
- Compara el trabajo de tus ideas con el tamaño máximo, como en el festival.
- Programa, prueba con los ejemplos y un caso borde propio.
- Envía. Si falla, el veredicto te dice dónde buscar.
🏋️ Práctica
Práctica directa: Elegir tipo y trabajo
Lee n y p con 0≤n≤10⁹, 1≤p≤10⁶; imprime n·p. Entrada: 1000000000 1000000. Salida: 1000000000000000.
Idea para comprobar tu solución
Un producto evita repetir mil millones de sumas, pero debe hacerse en long long desde el principio.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Gastón y las baldosas | Nacional 2018 | la fórmula antes que el ciclo |
| 2 | Cubiertos | Regional 2017 | reducir el enunciado a una línea |
| 3 | Cachipun | Nacional 2023 | restricciones que prohíben el O(n²) |
| 4 | Ricardo y su nóctulo | Regional 2024 | períodos y casos borde |
| 5 | ⭐ Baldosas | Regional 2024 | n·m hasta 10¹⁸: puro long long |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Team (231A) | ★ (800) | t casos, contar condiciones |
| 2 | Domino piling (50A) | ★ (800) | pensar la fórmula antes de codear |
| 3 | Weird Algorithm (CSES 1068) | ★ (—) | ciclo while, trampa de long long |
| 4 | Missing Number (CSES 1083) | ★★ (—) | fórmula n(n+1)/2, overflow |
| 5 | Required Remainder (1374A) | ★★ (800) | restricciones grandes ⇒ O(1) |
| 6 | ⭐ Theatre Square (1A) | ★★★ (1000) | redondeo hacia arriba + long long |
Un ejemplo para pensar
Un problema pide la suma de n números de hasta un millón. Una subtarea
permite n ≤ 100; la completa, n ≤ 200 000. Una solución recorre los
números una sola vez y acumula en un int de 32 bits. ¿Basta con que sea rápida?
Tiempo y rango son preguntas distintas
El recorrido hace como máximo 200 000 sumas, pero el resultado puede llegar a 200 000 000 000. La subtarea pequeña cabe en
int; la completa exige un tipo de mayor rango, comolong long. Un algoritmo puede tener una complejidad adecuada y aun así representar mal su respuesta. El tipo del acumulador se elige con la suma máxima, no con el tamaño de cada número por separado.
← 01 - Tu primer programa · Ruta de Aprendizaje · 03 - Arreglos y búsqueda lineal →