Introducción y generalidades

Muchos de los problemas que suelen aparecer en los concursos de programación requieren para su solución que el concursante aplique ciertas propiedades matemáticas. Estar familiarizado con los teoremas y propiedades que han aparecido en ediciones anteriores de los concursos aporta, por tanto, una clara ventaja. Además, es necesario saber cómo implementar correctamente programas que apliquen estas propiedades.

Dentro de los problemas que podríamos clasificar como «numéricos» o «geométricos» existe una gran heterogeneidad. Por ejemplo, podemos encontrar:

Problemas que explotan alguna propiedad de la teoría de números (divisibilidad, congruencias, números primos, aritmética modular…).
Problemas que requieren el manejo de números enteros que no se pueden representar directamente con los tipos de datos numéricos nativos de los lenguajes por ser demasiado grandes (o, equivalentemente, números racionales que necesitan más precisión de la disponible).
Problemas cuya solución pasa por encontrar las soluciones de alguna ecuación.
Problemas en los que hay que trabajar con polinomios, ya sea para evaluarlos o para operar con ellos (suma, resta, multiplicación y división de polinomios).
Problemas geométricos en los que es necesario calcular áreas o volúmenes, distancias, puntos de intersección de curvas o rectas, …
Problemas de trigonometría.

Los problemas numéricos y geométricos son normalmente fáciles de identificar. Sin embargo, no siempre es así: debido a que las matemáticas se pueden usar para casi todo, a veces se esconden problemas matemáticos detrás de descripciones que parecen no tener nada que ver.

Tipos de datos numéricos

A la hora de resolver un problema numérico es importante recordar cómo se representan los números en un computador y las limitaciones de las representaciones disponibles.

Números enteros

Los números enteros se representan usando binario natural (para los números sin signo) o complemento a dos (para los números con signo) y un número limitado de bits. Los tipos de datos disponibles y su rango dependen del lenguaje que estemos usando y de la plataforma usada para ejecutar el programa. En el caso de los jueces online usados en los concursos, debemos asumir que se tratan de máquinas de 32 bits (si fueran de 64 bits, los rangos serían mayores para algunos tipos).

En C y en C++ disponemos de los siguientes tipos cuyo tamaño y rango se muestran para una arquitectura de 32 bits:

Tipo	Tamaño	Rango representable
`char`	1 byte	-128 – 127
`int`	4 bytes	-2 147 483 648 – 2 147 483 647
`long`	4 bytes	-2 147 483 648 – 2 147 483 647
`long long`	8 bytes	-9 223 372 036 854 775 808 – 9 223 372 036 854 775 807
`unsigned char`	1 byte	0 – 256
`unsigned int`	4 bytes	0 – 4 294 967 296
`unsigned long`	4 bytes	0 – 4 294 967 296
`unsigned long long`	8 bytes	0 – 18 446 744 073 709 551 616

Debemos ser cuidadosos a la hora de elegir el tipo de las variable y pensar si alguno de los valores finales o intermedios de nuestro programa corre el riesgo de salirse del rango del tipo elegido.

Ni C, ni C++ ni Java permiten detectar cuándo se produce desbordamiento de forma automática (sí se puede hacer manualmente, pero no es práctico normalmente), por lo que no siempre es fácil detectar este tipo de problemas mediante pruebas. A veces se puede detectar cuando vemos que los resultados obtenidos no tienen sentido (por ejemplo, si el signo del resultado no es el que esperamos).

En ocasiones será necesario trabajar con cantidades demasiado grandes para poder ser representables mediante ninguno de los tipos anteriores y habrá que recurrir a otros tipos.

Números en coma flotante

Los números en coma flotante se representan usando el estándar IEEE-754. En C++ tenemos dos tipos que podemos usar:

Tipo	Tamaño	Rango representable	Precisión
`float`	4 bytes	-10³⁸ – 10³⁸ aproximadamente	24 bits significativos
`double`	8 bytes	-10³⁰⁸ – 10³⁰⁸ aproximadamente	53 bits significativos

Es importante tener en cuenta que los números en coma flotante no se comportan como los números reales a los que estamos acostumbrados habitualmente. Por ejemplo, debido a los redondeos se pierde precisión si se realizan sumas o restas entre números de tamaño muy diferente, incluso pudiéndose producir desbordamiento en algunos casos. De hecho, las operaciones de suma y resta no son asociativas (el orden en el que se realizan importa).

El error más típico a la hora de trabajar con números en coma flotante se produce a la hora de comparar (o comprobar si un número es 0). Hay que tener en cuenta que debido a la precisión, dos números que deberían ser iguales no siempre lo son, por lo que hay que siempre hay que admitir una cierta tolerancia. Es decir, si a y b son variables de tipo float, el siguiente código no es correcto:

if (a == c) printf("a y b son iguales");

En su lugar habría que usar algo parecido a lo siguiente:

#define TOLERANCIA 0.000001f

…

if (abs(a - c) < TOLERANCIA) printf("podemos considerar que a y b son iguales");

Números con precisión ilimitada

En ocasiones es necesario trabajar con números enteros demasiado grandes o con números decimales de gran precisión (los cuales se pueden codificar como un número entero grande acompañado de la posición de la coma). En estos casos, será necesario usar un tipo de datos específico.

C++ no incluye un tipo de datos en la librería estándar para este caso, por lo que conviene saber implementar uno. El entero grande (Big Integer) se implementará representando los números mediante arrays de cifras, pudiendo ser las cifras caracteres (usando base 10), bytes (usando base 256) o enteros (usando base 2³² ó 2⁶⁴). Una implementación de enteros grandes es, probablemente, una de las cosas que debería aparecer en los apuntes que cada concursante lleve consigo al concurso.

En el caso de Java se pude utilizar la clase java.math.BigInteger, por lo que puede ser aconsejable usar Java para resolver estos problemas si son sencillos.

Problema de ejemplo

En esta sesión vamos a analizar y resolver el problema «Sunny Mountains» que apareció en la fase nacional portuguesa de 2004 (MIUP 2004):

PROBLEMA 920. Sunny Mountains: Enunciado del problema - Enlace al juez

Este es un problema geométrico fácil de reconocer. Básicamente, nos están pidiendo que calculemos la longitud de los segmentos de ladera iluminados por el sol (resaltados en la figura incluida en el enunciado).

Resolución del problema

Tenemos que calcular la longitud de los segmentos de ladera iluminados por el sol. Para simplificar el problema, nos indican que los rayos del sol son horizontales. Esto nos permite determinar fácilmente la porción de ladera visible si hacemos un recorrido de los puntos de derecha a izquierda: será visible el trozo de ladera que quede por encima del pico más alto visitado hasta el momento. Por supuesto, si el pico de alguna montaña es más bajo que el de otra montaña más a su derecha, la ladera queda totalmente oculta y no es necesario procesarla.

Para encontrar la longitud de los segmentos iluminados, tenemos que ir considerando las cimas de dos en dos según se va haciendo el recorrido de derecha a izquierda. Como se muestra en la figura siguiente, se puede definir un triángulo rectángulo cuya hipotenusa es la ladera de la montaña actual y tiene como extremos la cima de la montaña anterior (marcada como prev) y la actual (marcada como current). Los catetos de este triángulo se han marcado en verde en la figura.

Figura explicativa del problema 920

Es fácil calcular la longitud de ambos catetos símplemente restando las coordenadas x e y de current y prev. Sería fácil, por tanto, calcular la longitud total de la ladera aplicando el teoréma de pitágoras. Sin embargo, estamos interesados solo en la longitud de la parte de la hipotenusa iluminada por el sol.

Si conocemos la altura de la cima más alta a la derecha de la actual (marcada como shadow_height en la figura), podemos definir otro triángulo rectángulo cuya hipotenusa sí es la que nos interesa. La longitud del cateto vertical de este triángulo más pequeño se puede calcular restándole shadow_height a la coordenada y de current. Para calcular la longitud del cateto horizontal (marcado en amarillo) tenemos que observar que ambos triángulos son semejantes, por lo que se mantendrá una relación de proporcionalidad entre los dos catetos verticales (los cuales ya conocemos) y los dos horizontales (de los cuales ya hemos calculado el mayor).

Una vez hallada la longitud de ambos catetos, calculamos la longitud de la hipotenusa y la sumamos a la longitud acumulada del resto de laderas iluminadas.

En la siguiente figura se muestra el código de un programa que resuelve este problema:

#include <iostream>
#include <vector>
#include <algorithm> // para sort
#include <cstdio> // para printf
#include <cmath> // para sqrt

using namespace std;

typedef pair<int, int> point;

int main (int argc, char *argv[]) {
  int nproblems;
  cin >> nproblems;
  for (int problem = 0; problem < nproblems; problem++) { 
    vector<point> mountains; // cada punto leído es la cima de una
                             // montaña, excepto el primero y el
                             // último.
    int npuntos;
    cin >> npuntos;
    for (int i = 0; i < npuntos; i++) { // leer cada punto
      int x, y;
      cin >> x; cin >> y;
      point p(x, y);
      mountains.push_back(p);
    }

    // ¡En el enunciado no dice que los puntos estén ordenados!
    // Aprovechamos que el tipo pair<A,B> define un operator< que
    // compara lexicográficamente. Los puntos quedarán ordenados de 
    // izquierda a derecha.
    sort(mountains.begin(), mountains.end()); 

    double meters = 0; // longitud visible acumulada.
    int shadow_height = 0; // altura del pico más alto visto hasta el
                           // momento, que tapa a todos los picos más
                           // bajos a su izquierda.
    // Hacemos un recorrido en orden inverso (de derecha a izquierda)
    // procesando dos puntos en cada iteración.
    for (vector<point>::reverse_iterator prev = mountains.rbegin(), current = prev + 1; 
         current != mountains.rend(); 
         current++, prev++) {
      if (current->second > shadow_height) {
	double width_total = prev->first - current->first;
	double height_total = current->second - prev->second;
	double height_visible = current->second - shadow_height;
	double width_visible = width_total * height_visible / height_total;
	double hyp_visible = sqrt(height_visible * height_visible + width_visible * width_visible);
	meters += hyp_visible;
	shadow_height = current->second;
      }
    }
    printf("%.2f\n", meters);
  }
  return 0;
}

En el programa anterior se utiliza el tipo pair<int, int> para representar los puntos. Alternativamente, se podría haber definido un struct con dos componentes (x e y), pero entonces también tendríamos que haber definido un operador de comparación ya que necesitamos ordenar la lista de puntos una vez leída.

Obsérvese también que se utiliza el tipo int para almacenar los puntos leídos, pero que todas las operaciones se realizan con el tipo double. En este problema concreto probablemente se podría haber utilizado el tipo float ya que sólo nos piden dos dígitos decimales en el resultado. Sin embargo, la única desventaja del tipo double respecto a float es su mayor tamaño en memoria, que casi nunca es relevante, mientras que usando el tipo float nos arriesgamos a introducir más errores de redondeo. En general, casi nunca es aconsejable usar el tipo float en un concurso.

Problemas propuestos

Para esta sesión se propone el siguiente problema:

PROBLEMA 301. : Enunciado del problema - Enlace al juez
Este problema requiere utilizar varios algoritmos geométricos y de grafos. Una versión simplificada de este problema apareció en la Olimpiada Murciana de Programación de 2009.

Problemas adicionales

PROBLEMA 900. Brick Wall Patterns: Enunciado del problema - Enlace al juez
Este es un problema sencillo. Se trata de identificar una famosa secuencia.

PROBLEMA 10042. Smith Numbers: Enunciado del problema - Enlace al juez
La única dificultad de este problema consiste en factorizar un número.

PROBLEMA 10200. Prime Time: Enunciado del problema - Enlace al juez
Problema también sencillo que requiere factorizar números enteros.

PROBLEMA 264. Count on Cantor: Enunciado del problema - Enlace al juez
Para este problema es necesario saber generar la secuencia de Cantor.

PROBLEMA 113. Power of Cryptography: Enunciado del problema - Enlace al juez
Un problema en el que hay que utilizar aritmética modular.

Olimpiada de programación- Facultad de Informática - Universidad de Murcia