NAV
Introducción a la programación competitiva
Python 3 C++11

Introducción

ACM-ICPC World Finals 2018

icpc.baylor.edu

¿Qué es esto de programación competitiva?

La programación competitiva es un deporte mental donde los competidores tienen que programar para resolver un conjunto de problemas lo más rápido posible.

Los problemas son problemas conocidos de ciencia de la computación, y por conocidos quiero decir que ya tienen solución. Por lo menos el creador de los problemas (problem setter) los ha resuelto.

Resolver un problema significa escribir un programa que lea unos datos de entrada (input) y produzca unos datos de salida (output) según la descripción del problema. Una vez se haya resuelto un problema este será enviado a un juez (judge) para su revisión. El juez ejecutará el programa con varios casos de prueba y verificará que la salida sea igual a la salida dada por el problem setter. Finalmente, el juez le responderá al competidor que envió el programa si su solución es correcta o no.

Quién resuelva correctamente la mayor cantidad de problemas en el menor tiempo posible gana.

¿Y por qué debería competir o entrenar?

Hay bastantes beneficios de practicar la programación competitiva, por ejemplo:

Y hay muchas más razones, sin olvidar por supuesto que es bastante entretenido.

Bien, ¿hay algún pre-requisito?

#include <iostream>
using namespace std;

int my_pow(int x, int p)
{
    if (p == 0) return 1.0;
    if (p == 1) return x;
    int a = my_pow(x, p / 2);
    return a * a * (p % 2 == 0 ? 1 : x);
}

int main()
{
    int n;
    cin >> n;

    while(n--)
    {
        int x, p;
        cin >> x >> p;
        cout << my_pow(x, p) << endl;
    }

    return 0;
}

def my_pow(x, p):
    if p == 0: return 1
    if p == 1: return x
    a = my_pow(x, p // 2)
    return a * a * (1 if p % 2 == 0 else x)

n = int(input())

for _ in range(n):
    x = int(input())
    p = int(input())
    print(my_pow(x, p))

Hay algunos requisitos básicos:

En esta introducción te enseñaré algunos conceptos de programación, pero ya deberías entender lo que son variables, tipos de datos, operadores, estructuras de control de flujo (if, else, for, while, etc.), funciones, arreglos, entrada y salida, módulos (import, include), clases o estructuras, etc.

Si todavía no conoces todos esos conceptos no hay problema, puedes ir revisando tutoriales de programación en el camino. Por ahora entender el código de la derecha debería ser suficiente.

¿Qué lenguajes de programación puedo usar?

Los lenguajes de programación que usaré en este documento son Python 3 y C++11. Elegí estos lenguajes porque Python suele ser el primer lenguaje que enseñan en la universidad, y C++ es probablemente el lenguaje más usado en el mundo de la programación competitiva. Sin embargo, tú puedes usar el lenguaje que gustes, pero te recomiendo escoger uno de estos:

Listo esos lenguajes porque son los permitidos en los concursos del ACM-ICPC. El ICPC es el concurso de programación más importante y más adelante escribiré de él. Si quieres saber más sobre el ambiente de programación del ICPC (software instalado, versiones de los lenguajes, flags de compilación, etc.) revisa estas reglas.

Ahora estamos listos para resolver nuestro primer problema.

El primer problema

Problema

Watermelon

One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.
Pete and Billy are great fans of even numbers, that’s why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that’s why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.
Input
The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the boys.
Output
Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.
Examples
Input:
8
Output:
YES

Vamos a resolver nuestro primer problema, el problema 4A de Codeforces, Watermelon. Lo copio a la derecha por conveniencia.

Los problemas tienen 4 partes: enunciado, entrada, salida, y ejemplos.

Los problemas también suelen tener indicado el tiempo límite y el límite de memoria, es decir, nuestro programa no puede demorar más de ese tiempo ni usar más memoria de la indicada.

Solución

#include <iostream>
using namespace std;

int main()
{
    int w;
    cin >> w;

    if (<condición>)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}

w = int(input())

if <condición>:
    print('YES')
else:
    print('NO')

Después de leer el problema trata de resolverlo en tu lenguaje favorito. La solución debería verse similar al código de la derecha. Una vez hayas terminado tu código envíalo (submit) al juez para que lo pruebe (tienes que registrarte primero).

El juez te dirá si tu código está bien (Accepted) o no. Listaré algunos de los problemas comunes por los que tu programa podría fallar:

Si todavía no puedes resolverlo te dejo la solución para que veas donde te equivocaste:

El problema te pregunta si existen dos números enteros positivos y pares tales que su suma sea w. Los números existen si w es par excepto por el valor 2 (la única posibilidad sería 1 y 1, pero 1 no es par). Entonces, la condición que tienes completar en el código es w % 2 == 0 and w != 2.

¡Enhorabuena! Ya has debido resolver tu primer problema. Si quieres resolver más esta es una lista de los problemas en orden de dificultad.

Jueces en línea

Los jueces en línea (online judges) son sitios web donde puedes encontrar problemas para resolver y enviar tus soluciones.

Hay una gran cantidad de online judges, pero voy a ir listando los que vamos a ir usando.

Codeforces

Codeforces es un juez ruso que aparte de tener una gran variedad de problemas realiza contests en línea con problemas nuevos de forma seguida. Luego de que terminan los contests publican una editorial con la solución a los problemas. También te permite ver el código de los demás usuarios y (parcialmente) los casos de prueba de los problemas. Por eso este juez es uno de los mejores para aprender.

A2 Online Judge

A2 OJ, también conocido como Ahmed Aly, su creador, no tiene muchos problemas para resolver, pero permite crear contests en línea al estilo ICPC con problemas de otros jueces para entrenar. También tiene una muy útil lista de problemas por categoría.

UVa Online Judge

UVa, juez de la Universidad de Valladolid, uno de los más populares. Tiene una gran cantidad de problemas y es el juez usado en los libros de Competitive Programming de Steven Halim. También tiene un foro donde puedes discutir los problemas y uDebug, un sitio web donde puedes enviar la entrada de problemas y ver cuál es la salida correcta. Recomiendo usar uHunt para buscar problemas, tiene una interfaz más amigable que la del juez.

Otros jueces

Respuestas del juez

Estas son unas de las respuestas que el juez les puede dar sobre su solución:

Entrada y salida

Standard Streams

wikimedia.org

Los problemas siempre mencionan que la entrada debe ser leída del standard input y la salida debe ser impresa en el standard output, pero ¿qué significa eso? El standard input o stdin es un archivo especial al que podemos acceder desde nuestro programa para leer de él. De igual forma, el standard output o stdout es otro archivo especial en el que podemos escribir.

Cuando ejecutamos un programa desde la terminal el intérprete de la línea de comandos (shell) asigna el archivo stdin a la entrada de teclado y el archivo stdout a la pantalla de la terminal. Eso quiere decir que lo que escribamos en la terminal podrá ser leído del archivo stdin y lo que imprimamos al archivo stdout será mostrado en la pantalla.

Y ¿cómo leemos y escribimos a esos archivos? Pues ya lo hemos estado haciendo. Para leer del archivo stdin en Python usamos la función input(), y en C++ el objeto cin. Asimismo, para imprimir al archivo stdout usamos la función print() y el objeto cout.

Fin de archivo

Hay ciertos problemas que no indican que tan larga es la entrada y por lo tanto debemos leer hasta que termine el archivo. Para saber si el archivo ha terminado existe una marca especial llamada end-of-file o EOF que debemos detectar.

En Python se puede iterar todo el objeto archivo (file object) stdin del módulo sys, él mismo ya sabe cuando termina. En C++ lo recomendado es chequear el objeto cin como un valor booleano, si te da false significa que llegamos al final.

Si estás confundido no te preocupes, los ejemplos te mostrarán cómo hacerlo.

Si quieres ingresar manualmente un EOF desde la terminal deberás usar la combinación de teclas Ctrl + D en Linux o Ctrl + Z en Windows.

Entrada

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    // ...
}

from sys import stdin

# ...

Aquí te dejo unos ejemplos de entrada comunes y su código para leerlos. Ten en cuenta que la forma expuesta no es la única para leer del stdin y que la lista de ejemplos está lejos de estar completa.

Vas a encontrar problemas con los que tendrás dificultades con la entrada. Cuando esto suceda dale una leída a la documentación de entrada y salida de Python o C++ y trata de eliminar esas dificultades.

Los ejemplos de Python necesitan importar stdin del módulo sys y los de C++ incluir las cabeceras iostream, string y sstream.

Ejemplo 1

int a, b;
while (cin >> a >> b)
{
    // ...
}

for line in stdin:
    a, b = map(int, line.split())
    # ...

La entrada contiene múltiples casos de prueba, una línea por cada caso. Cada línea consiste de dos enteros a y b separados por un espacio.

Ejemplo 2

int N;
int a, b;

cin >> N;

for (int t = 0; t < N; ++t)
{
    cin >> a >> b;
    // ...
}

N = int(input())

for _ in range(N):
    a, b = map(int, input().split())
    # ...

La entrada contiene un entero N en la primer línea, y luego N líneas continúan. Cada línea consiste de un par de enteros a y b, separados por un espacio.

Ejemplo 3

int a, b;

while (cin >> a >> b && !(a == 0 && b == 0))
{
    // ...
}

while True:
    a, b = map(int, input().split())

    if a == 0 and b == 0:
        break

    # ...

La entrada contiene múltiples casos de prueba, una línea por cada caso. Cada línea contiene un par de enteros a y b separados por un espacio. Un caso de prueba con los valores 0 0 indica el fin de la entrada y no deberá ser procesado.

Ejemplo 4

int N;

while (cin >> N && N != 0)
{
    vector<int> a(N);

    for (int i = 0; i < N; ++i) cin >> a[i];

    // ...
}

for line in stdin:
    N, *a = map(int, line.split())

    if N == 0:
        break

    # ...

La entrada contiene múltiples casos de prueba, una línea por cada caso. Cada línea contiene un entero N seguido de N enteros. Un caso de prueba empezando con 0 indica el fin de la entrada y no deberá ser procesado.

La sintaxis a, *b = ... se llama extended iterable unpacking.

Ejemplo 5

string line;

while (getline(cin, line))
{
    stringstream ss(line);
    vector<int> a;
    int x;

    while(ss >> x) a.push_back(x);

    // ...
}

for line in stdin:
    a = map(int, line.split())

    # ...

La entrada contiene múltiples casos de prueba, una línea por cada caso. Cada línea consiste de una lista de enteros separados por un espacio.

stringstream es una clase similar a la de cin y cout que escribe o lee a un string en vez de a un archivo. En este caso lo iniciamos con el string que nos da getline y luego extraemos los enteros uno por uno.

Ejemplo 6

int T;

cin >> T;
cin.get();

while (T--)
{
    string line;

    while (getline(cin, line) && !line.empty())
    {
        stringstream ss(line);
        vector<string> words;
        string word;

        while(ss >> word) words.push_back(word);

        // ...
    }    
}

T = int(input())

for _ in range(T):
    while True:
        line = input()

        if not line:
            break

        words = line.split()

        # ...

La primer línea de la entrada es el número de casos de prueba, T. Cada caso de prueba consiste de varias líneas, cada línea consiste de una o varias palabras separadas por uno o más espacios. Los casos de prueba están separados por una línea en blanco.

Fíjate en la llamada a cin.get(). El método get() extrae un carácter de la entrada. En este caso ese carácter es el salto de línea '\n' que está después de T. Si no extraemos ese salto de línea la llamada que hacemos luego a getline() sería un string vacío.

Salida

La salida de los problemas no suele traer tantas dificultades, pero a veces pueden pedir un formato en especial.

Algo a tomar en cuenta son los saltos de línea o espacios demás. Los jueces modernos no le dan mucha importancia a si hay un salto de línea al final de la salida o no, pero hay problemas o jueces en los que eso te puede dar presentation error o incluso wrong answer.

Ejemplo 1

vector<string> words = {"alice", "bob", "charlie"};

for (string &word : words) cout << word << "\n";

words = ['alice', 'bob', 'charlie']
print('\n'.join(words))

alice
bob
charlie
<línea en blanco>

Imprimir una lista de palabras con un salto de línea después de cada una.

Ejemplo 2

vector<int> numbers = {1, 6, 1, 8, 0};
string sep = "";

for (int number : numbers)
{
    cout << sep << number;
    sep = ", ";
}

numbers = [1, 6, 1, 8, 0]
print(', '.join(map(str, numbers)), end='')

1 6 1 8 0

Imprimir una lista de enteros separados por una coma y un espacio. No imprimir una línea en blanco al final.

En Python 3 la función print() imprime un salto de línea al final, si quieres evitar eso puedes hacerlo con el parámetro end. Por ejemplo, print('Hi', end='!') imprimirá un ! inmediatamente después de Hi sin ningún salto de línea.

Ejemplos de formato

#include <iostream>
#include <iomanip>
#include <string>
#include <bitset>
using namespace std;

int main()
{
    int answer = 42;
    double phi = 1.618033989;

    cout << "Answer: " << answer << "\n";
    cout << "Binary: " << bitset<8>(answer) << "\n";
    cout << "Hexadecimal: 0x" << hex << uppercase << answer << "\n";
    cout << "With zeroes: " << dec << setw(4) << setfill('0') << answer << "\n";
    cout << "Positive sign: " << setw(8) << internal << showpos << setfill('_') << answer << "\n";
    cout << "Padding: " << setw(6) << left << noshowpos << setfill('-') << answer << "\n";
    cout << dec << right << noshowpos << nouppercase << setfill(' ') << "\n"; // Reset

    cout << "Golden ratio: " << phi << "\n";
    cout << "Less precision: " << fixed << setprecision(3) << phi << "\n";
    cout << "No precision: " << fixed << setprecision(0) << phi << "\n";
    cout << "With zeroes: " << fixed << setprecision(3) << setw(7) << setfill('0') << phi << "\n";
    cout << "Scientific: " << scientific << phi;
    cout << defaultfloat << setprecision(6) << setfill(' '); // Reset
    return 0;
}

answer = 42
phi = 1.618033989

print('Answer: {:d}'.format(answer))
print('Binary: {:08b}'.format(answer))
print('Hexadecimal: 0x{:X}'.format(answer))
print('With zeroes: {:04d}'.format(answer))
print('Positive sign: {:_=+8d}'.format(answer))
print('Padding: {:-<6d}'.format(answer), end='\n\n')

print('Golden ratio: {:.5f}'.format(phi))
print('Less precision: {:.3f}'.format(phi))
print('No precision: {:.0f}'.format(phi))
print('With zeroes: {:07.3f}'.format(phi))
print('Scientific: {:.3e}'.format(phi), end='')

Answer: 42
Binary: 00101010
Hexadecimal: 0x2A
With zeroes: 0042
Positive sign: +_____42
Padding: 42----
<línea en blanco>
Golden ratio: 1.61803
Less precision: 1.618
No precision: 2
With zeroes: 001.618
Scientific: 1.618e+00

En Python lo mejor es usar el método format de los strings. PyFormat es un cheat sheet con varios ejemplos.

En C++ se utiliza lo que se llama manipuladores de salida. Estos manipuladores son objetos o funciones que modifican al flujo (por ejemplo cout o un objeto de la clase stringstream) causando que imprima de manera diferente. Los manipuladores que más usarás son:

Ten en cuenta que los manipuladores, excepto por setw, no son temporales, van a afectar todo lo que imprimas después de ser usados. Si tienes que imprimir algo después “sin formato” tendrás que revertir los cambios.

Te recomiendo que juegues con el código de la derecha cambiando valores y probando otros manipuladores o strings de formato.

En C++ también puedes usar printf() para imprimir con formato. printf() es más simple que los manipuladores de salida, pero no es buena idea mezclarlo con cout. Solo usa uno de los dos.

Salida de errores

#include <iostream>
using namespace std;

int main()
{
    cerr << "bugs" << endl;
    return 0;
}

from sys import stderr

print('bugs', file=stderr)

La salida de errores o stderr es otro archivo especial donde podemos escribir errores o mensajes de debug. Al igual que con el stdout los mensajes saldrán en la pantalla, pero estos no serán leídos por el juez (recuerda que él solo lee el stdout). De esta forma no tendremos que preocuparnos de que un mensaje extra escrito en el stderr nos cueste una solución correcta.

Enlaces externos

Tutoriales de programación

Python

El tutorial oficial de Python es bastante bueno y vale la pena leerlo. También está la versión en español de Python Argentina.

Si ya conoces otros lenguajes de programación y quieres aprender Python te recomiendo que leas estos enlaces:

Si Python es tu primer lenguaje de programación estos libros son buenos:

Si quieres ver más recursos chequea estás listas:

Pero ten en cuenta que algunos de esos recursos son bastante antiguos, por lo menos escoge un libro o tutorial que enseñe Python 3. Ya no es recomendado usar Python 2.

C++

Para aprender C++ no puedo recomendar ninguno de los tutoriales en línea que se encuentran por ahí. Lo mejor es aprender de un libro.

Si no tienes experiencia de programación te recomiendo uno de estos:

Si ya sabes algo de programación te recomiendo The C++ Programming Language, 4th edition de Stroustrup, el creador de C++.

Los libros que nombré enseñan C++11. C++11 ha cambiado el lenguaje de forma significante, y por eso recomiendo leer un libro de C++11 y no de C++98 o (C++03). También existen C++14 y C++17. C++14 es solo una extensión menor de C++11, es decir no ha habido muchos cambios. C++17 introduce nuevas características, pero el estándar recién fue publicado en diciembre de 2017, el soporte de estas características en los compiladores todavía es experimental y no hay muchos libros que cubran C++17. De cualquier forma C++17 no se utiliza en el ICPC, claro que eso no quiere decir que sea mala idea ir revisándolo.

Si quieres ver otros recursos revisa estos enlaces:

Acerca de

Este documento se continúa escribiendo y espero que algún día llegue a estar algo terminado y pueda ser de ayuda a los estudiantes que quieran iniciarse en el mundo de la programación competitiva.

Si encuentras algún error, o crees que haya algo que se pueda mejorar puedes dejar un issue en el repositorio. Pull requests también son bienvenidos.

kevinz

Licencia

Esta obra está bajo una licencia de Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

Licencia de Creative Commons

Python 3 C++11