Tipos de datos

C++JavaPython

Recursos
Fuente	Recurso	Notas
CPPR	Fundamental Types	tamaños + rangos
IUSACO	2.2 - Data Types	este módulo se basa en esto
CPH	1.3 - Working with numbers	Enteros, aritmética modular, números de punto flotante
PAPS1	2.2 - Variables & Types	muchos ejercicios

C++: tipos de datos fundamentales habituales

Nota: Estos números pueden variar según la máquina y/o el compilador. Para más tipos de datos fundamentales, consultar el primer recurso de la tabla de arriba.

Tipos	`int`	`long long`	`double`	`bool`	`char`
Descripción	entero de 32 bits	entero de 64 bits	flotante de doble precisión	valor verdadero/falso	carácter de 8 bits
Tamaño (bytes)	4	8	8	1	1
Rango	$-2^{31}$ a $2^{31}-1$	$-2^{63}$ a $2^{63}-1$	`-1.7E+308` a `+1.7E+308`	$0$ o $1$ (`true` o `false`)	$-2^7$ a $2^7-1$

Recursos
Fuente	Recurso	Notas
JavaDocs	Primitive Data Types
IUSACO	2.2 - Data Types	este módulo se basa en esto

Java: tipos de datos primitivos habituales

Para más tipos de datos primitivos, consultar el primer recurso de la tabla de arriba.

Tipos	`int`	`long`	`double`	`boolean`	`char`
Descripción	entero de 32 bits	entero de 64 bits	flotante de doble precisión	valor verdadero/falso	carácter Unicode de 16 bits
Tamaño (bytes)	4	8	8	1 bit(*)	2
Rango	$-2^{31}$ a $2^{31}-1$	$-2^{63}$ a $2^{63}-1$	`-1.7E+308` a `+1.7E+308`	true/false	`\u0000` a `\uffff` ( $0-65535$ )

*Nota: Es poco probable que los booleanos usen realmente solo 1 bit de memoria, ya que en la mayoría de los casos los tipos de datos deben alinearse a bytes. Sin embargo, solo se puede almacenar un bit de información en ellos.

Recursos
Fuente	Recurso	Notas
IUSACO	2.2 - Data Types	este módulo se basa en esto
Python	Built-in Types

Tipos	`int`	`float`	`bool`	`str`
Descripción	entero de tamaño arbitrario	flotante IEEE 754 de doble precisión (64 bits)	valor verdadero/falso	string
Valores	cualquier entero	`-1.7E+308` a `+1.7E+308`	true/false	texto de cualquier longitud

Hay varios tipos de datos principales que se usan en contests: enteros, números de punto flotante, booleanos, caracteres y strings. Si ya se conoce el lenguaje que se está usando, esto debería ser en su mayoría repaso.

El entero de 32 bits habitual (int en C++ y Java) admite valores entre $-2\,147\,483\,648$ y $2\,147\,483\,647$ , lo que es aproximadamente igual a $\pm 2 \cdot 10^9$ .

Algunos problemas exigen usar enteros de 64 bits (long long en C++ y long en Java) en lugar de enteros de 32 bits (int). Los enteros de 64 bits tienen menos probabilidad de desbordarse, ya que pueden almacenar cualquier número entre $-9\,223\,372\,036\,854\,775\,808$ y $9\,223\,372\,036\,854\,775\,807$ , que es aproximadamente igual a $\pm 9 \times 10^{18}$ . En Python, los int tienen tamaño ilimitado.

A veces (pero no siempre) el enunciado de un problema de USACO (p. ej. Haircut ) incluye una advertencia como la siguiente:

Nótese que el gran tamaño de los enteros involucrados en este problema puede exigir tipos de datos enteros de 64 bits (p. ej., un “long long” en C/C++).

Los problemas de contest suelen estar planteados de modo que el entero de 64 bits alcance, así que en las divisiones más bajas puede ser buena idea usar enteros de 64 bits en lugar de enteros de 32 bits en todas partes. Por supuesto, no hay que hacerlo cuando los límites de tiempo y/o memoria están ajustados, lo que puede ocurrir en las divisiones más altas de USACO. También hay que tener en cuenta que en Java hace falta hacer un cast de long a int al acceder a índices de arreglos.

Además existen enteros de 16 bits (short en C++ y Java). Sin embargo, en general no son útiles, porque la memoria extra que se ahorra al usarlos suele ser despreciable. También existen enteros sin signo (unsigned int, unsigned long long, etc.). No se usan tan a menudo, aunque el aumento de tamaño al doble a veces es la diferencia entre desbordarse y no desbordarse.

Los números de punto flotante se usan para guardar valores decimales. Es importante saber que los números de punto flotante no son exactos, porque la arquitectura binaria de las computadoras solo puede almacenar decimales hasta cierta precisión. Por eso, siempre hay que esperar que los números de punto flotante estén un poco desviados, y en general es mala idea comparar dos números de punto flotante por igualdad exacta (==).

Los problemas de contest suelen acomodar la imprecisión de los números de punto flotante comprobando si la diferencia absoluta o relativa entre la salida y la respuesta es menor que alguna constante pequeña como $\epsilon=10^{-9}$ .

Si la salida es $x$ y la respuesta es $y$ , la diferencia absoluta es $|x-y|$ .
Si la salida es $x$ y la respuesta es $y$ , la diferencia relativa es $\frac{|x-y|}{|y|}$ .

Esto no ocurre en USACO, donde los problemas en general tienen una salida correcta única. Así, cuando hace falta punto flotante, el formato de salida suele ser algo del estilo de “Imprimir $10^6$ veces la probabilidad máxima de recibir exactamente una invitación aceptada, redondeada hacia abajo al entero más cercano.” (p. ej. Cow Dating ).

Las variables booleanas tienen dos estados posibles: true y false. En general usamos booleanos para marcar si un cierto proceso ya terminó, y arreglos de booleanos para marcar qué componentes de un algoritmo ya terminaron. Los booleanos requieren 1 byte (8 bits) de almacenamiento, no 1 bit, desperdiciando los otros 7 bits de almacenamiento. Para usar menos memoria, se pueden usar bitsets (std::bitset en C++ / BitSet en Java). Lamentablemente, los bitsets no están disponibles en Python.

Las variables de carácter representan un solo carácter. Se obtienen al acceder al carácter de un índice dado dentro de un string. Los caracteres se representan con el estándar ASCII, que asigna a cada carácter un entero correspondiente. Esto permite hacer aritmética con ellos; por ejemplo, tanto cout << ('f' - 'a'); en C++ como System.out.print('f' - 'a'); en Java imprimen 5. En Java, los caracteres ocupan 16 bits, mientras que en C/C++ ocupan 8 bits.

Los strings son, en la práctica, arreglos de caracteres. Se puede acceder fácilmente al carácter de un índice dado y tomar subcadenas del string (charAt() y substring() en Java).