Ronda 1ª-1: El etiquetador loco

Enunciado original.

El problema de menos valor de la ronda (15 puntos) y el más simple de los cuatro. Con unas matemáticas detrás de él muy asequibles y un algoritmo sencillo.

Por si alguno lo ha pensado es inviable ir simulando todas las etiquetas y contándolas hasta que lleguemos a la cantidad pedida. 2⁶³ es un número increíblemente grande como para pensar en contarlo.
Un número tan grande que necesitamos un tipo de datos especial. El último de los llegados a los lenguajes C, hasta el momento, en la categoría de enteros.
Aprovechemos la excusa para repasar estos tipos que son la base de la programación. Hay que pensar que en el ordenador la memoria se organiza en celdas en las que se guardan enteros y con ellos se modelan todos los tipos de datos. Incluso los primeros microprocesadores, allá en la época que comencé a programar cuando tenían 8 bits (y algunos 4), sólo podían hacer operaciones con enteros. Las operaciones con reales se realizaban mediante llamadas a librerías que hacían infinidad de operaciones con enteros. Afortunadamente teníamos ya los compiladores que se ocupaban de estos detalles (como ahora).

Tipos de datos enteros

Los tipos de datos enteros normales que podemos manejar en C++ son: char, short, int, long y, el que necesitaremos para este problema, el long long, que como su propio nombre indica es muy largo.

Podemos encontrarnos el tipo long especificado a veces como long int para recordarnos que es un tipo mayor que el simple int. Como a mí no me gusta escribir de más jamás empleo esta forma de escribir el tipo.

Esperamos encontrar que el tipo char ocupa 8 bits, los tipos short e int ocupan 16, el tipo long 32 y el gigante de los tipos, el long long, 64 bits. Pero cada compilador para cada procesador y en cada sistema operativo pueden asignar distintos tamaños para estos tipos, aunque los valores indicados aquí son valores mínimos que vamos a encontrar, es decir, cuando especificamos una variable int sabemos que como mínimo tendremos 16 bits disponibles, aunque en la actualidad muchos compiladores reservan 32 bits para este tipo.

Otra cosa que tenemos seguro es que el tamaño de los tipos sigue el orden especificado en la lista, es decir, el tipo short no puede ser más grande que el int.

Los números negativos se representan con el bit de mayor peso a uno y los positivos a cero, por lo tanto tenemos disponibles un bit menos para representar el valor absoluto del dato. Así si un dato ocupa 16 bits nos quedaran 15 para especificar el número sin el signo. Es decir, en este caso se pueden almacenar valores desde -2¹⁵ (-32768) hasta 2¹⁵-1 (+32767). ¿Por qué llegamos más lejos con los números negativos que con los positivos? No porque el ordenador sepa que estamos la mayor parte del tiempo en números rojos en nuestra cuenta sino porque el cero nos ocupa una posición entre los positivos.

En los tiempos en los que la memoria era un bien escaso se pensó que para muchas situaciones sólo necesitamos números positivos y era un desperdicio enorme perder 1 bit de memoria en cada posición. Así que se habilitó el prefijo unsigned que se puede anteponer a todos los tipos para indicarle al compilador que ese tipo de datos no tiene números negativos y el bit de mayor peso no es el signo sino parte del valor. Con este truco, en el ejemplo anterior, aumentamos el número máximo que se puede almacenar hasta 65535 (entre 0 y 65535).
¿Por qué esta indeterminación en los tamaños? Supongo que será para aprovechar mejor las posibilidades del procesador para el que se compile el fuente. Si el procesador en el que se va a ejecutar el programa maneja igual o mejor los datos de 32 bits que los de 16 ¿por qué forzarnos a manejar datos más pequeños?
¿Puede ser un problema tener esta indeterminación en los tamaños? Seguramente en algunos casos sí. Para poder emplear toda la información del tamaño de cada tipo y los valores mínimo y máximo que pueden almacenar tenemos constantes definidas en el fichero de cabecera climits (limits.h para C) cuya definición se puede ver aquí.
En nuestro programa necesitaremos conocer el límite superior de las variables de tipo unsigned long long que  emplearemos para los cálculos. Lo obtendremos de la constante ULONGLONG_MAX.

Algoritmo

No creo necesario explicar que las cajas que podemos etiquetar de forma diferente con un conjunto de L letras usando n de ellas es de L^n (L elevado a n). Si alguien no se lo cree puede mirarlo aquí.

El algoritmo que emplearemos es el siguiente:

Tomaremos el número de cajas a etiquetar (N) y le restamos una, la caja de la cual queremos saber la etiqueta.

A continuación vamos calculando las permutaciones con repetición (que es el nombre más preciso de las combinaciones de etiquetas) de L elementos (las letras que funcionan en la etiquetadora) cogidos primero de una en una (L), luego de dos en dos (L²) y así sucesivamente y vamos restando del total de cajas cada cantidad hasta el número de letras (n) en que las cajas restantes sean menores que las combinaciones que se  generan con las letras tomadas de n en n.

En este punto ya sabemos cuántas letras tendrá la etiqueta de la última caja, pero ahora nos falta saber cuál será esa etiqueta.

Aunque ya tengamos muchas menos combinaciones sigue siendo inviable ir generando todas las combinaciones. Así que pensemos en otra forma de saberlo.

En realidad el procedimiento a seguir será muy parecido al descrito antes.
Veamos el primer carácter. Con cada carácter de la primera posición tenemos L^(n-1) combinaciones de los n-1 caracteres restantes. Así que si dividimos las N cajas cajas que quedan por etiquetar para esta cantidad obtendremos el índice del primer carácter de la etiqueta de la caja final comenzando la primera letra con el índice cero. El resto de esta división serán las cajas que quedarán cuando comencemos con la letra obtenida. Así que la segunda letra de la etiqueta repetiremos el mismo proceso tomando las cajas restantes igual al resto.

Programa

Comenzamos como siempre con el bucle para los casos y la lectura de datos. No vamos a entrar en más detalles.

Como hemos visto en el algoritmo vamos a necesitar dos bucles, pero antes necesitaremos unas operaciones previas:

for (m=0; L[m]!=0; m++);  // count good keys

v[0]=m; // 1-key combinations

n=0;

N--; // boxes except the last one

La primera instrucción en un bucle que no hace nada. Por eso el final de instrucción (;) detrás de la cabecera del bucle. ¿Pero realmente no hace nada? Evidentemente no. Va a contar los caracteres que tiene la cadena de caracteres leída en el array L (char L[120]). En C++ (como en C) las cadenas de caracteres terminan con el carácter especial \x0, o sea el carácter con valor ASCII cero.

Así el bucle va incrementando la variable entera m hasta que el carácter del array en la posición m-ésima es el carácter especial final de cadena. Hay que recalcar que es seguro que el carácter final de cadena se va a encontrar al final (siempre que el tamaño de la cadena no exceda la capacidad del array) por lo que no implementamos ningún control de error para el caso de que no estuviera este carácter. Observad también que la comparación está escrita como si el contenido del array L fueran enteros. Los tipos char y unsigned char tienen la dualidad de poder trabajar con ellos como caracteres o como enteros.

Como el primer carácter del array tiene índice cero, en m obtendremos el número de caracteres de la cadena, es decir, el número de letras buenas de la etiquetadora.

En las especificaciones se fija que el número máximo de letras de la etiquetadora será de 25, así que necesitaríamos un array de, como mínimo, 26 puesto que no hay que olvidar que el array debe poder almacenar el carácter cero (a veces llamado nulo) de final de cadena. ¿Por qué lo dimensioné de 120? Ni idea. seguramente porque como me sobra la memoria...

A continuación inicializo el primer elemento del array v de tipo unsigned long long al valor m. Como se ve en la descripción del algoritmo vamos a necesitar las potencias del número de letras de la etiquetadora en los dos bucles, así que en lugar de calcularlas dos veces decidí calcularlas una sola y guardarlas en un array, es una cantidad irrisoria de memoria aunque también es un ahorro de tiempo ridículo en el programa el que nos reportará, puesto que nos ahorraremos una división por letra de la etiqueta final.

Las sucesivas potencias se calcularán multiplicando por m el valor de la potencia anterior. Es decir calcularemos m^n como m*m^(n-1). Si no guardásemos todas las potencias haríamos lo mismo y en el segundo bucle, que como vemos vamos necesitando las potencias de índice cada vez menor, lo calcularíamos como m^(n+1)/m.
La última inicialización es restar uno a las cajas para quitar la última, que es de la que queremos calcular la etiqueta, del cálculo. En realidad esta línea la añadí al final del programa. Esta es una de esas situaciones en las que dudas si con al algoritmo que has implementado deberías usar N o N-1 como dato. En vez de perder tiempo en pensar sobre ello te dejas una nota y, cuando pruebes el programa, si ves que el resultado que obtienes está desfasado en una unidad actúas en consecuencia. Es la gran ventaja de la programación como disciplina, te permite el método de ensayo y error que, por ejemplo, para un piloto aterrizando un avión no es recomendable.
Codifiquemos el primer bucle del algoritmo:

while (N>=v[n])  // how many keys we need
{
N-=v[n];  // boxes labeleds
v[n+1]=v[n]*m;  // variations with one more letter
n++;
}

Vamos restando a N las distintas potencias de m que equivalen al conjunto de cajas etiquetadas con las permutaciones de m elementos tomados de n en n. Usamos la potencia calculada en la iteración anterior y calculamos la potencia de la siguiente. Por ello el bucle termina en el momento que el valor de la potencia que vamos a emplear es mayor que el número de cajas restantes, lo que equivale a decir que es la cantidad de letras en la etiqueta cuyas permutaciones no vamos a terminar.
¿Es esta implementación correcta? Parece que sí y, de hecho, funcionará en la mayor parte de los casos, pero no en todos. Por lo tanto no es correcta. He de admitir que esta fue la versión del programa con la que me descargué el fichero de datos del concurso y que, por supuesto no me funcionó y tuve que modificar en los 6 minutos de la cuenta atrás. ¡Una locura de nervios!
¿Dónde está el fallo?
Es fácil ver que estamos calculando una potencia más de la que necesitamos puesto que es cuando calculamos esa potencia que se pasa del valor de N cuando nos damos cuenta que el bucle ha terminado. Con los límites del problema habíamos llegado a la correcta conclusión que todos los cálculos que tuvieran que ver con el número de cajas, como las potencias que vamos calculando, nos caben en una variable de tipo unsigned long long, por lo tanto la última potencia que empleemos sí cabrá en esta variable pero ¿alguien nos asegura que la siguiente potencia, la que va a ser mayor que el número de cajas, también va a caber? La respuesta es no. Puede haber casos en que esa siguiente potencia no quepa en tal variable y las retorcidas mentes del concurso lo encontraron y lo propusieron.
La dificultad era que como usé las opciones optimizadas del compilador, el programa no comprueba que el resultado de una operación sea mayor que el máximo por optimización del tiempo, en lugar de arrojar un error lo que hace es devolver un número erróneo y que no cumple con la condición de final de bucle, posponiendo el error. Afortunadamente, en mi compilador, el número que me devolvía el cálculo era cero, con lo que el resto de potencias valía cero, el bucle no terminaba nunca y obtenía un error de ejecución cuando comenzaba a escribir ceros más allá del límite del array v.
¿Qué se me ocurrió para resolverlo? Pues calcular el valor máximo del cual podría calcular la siguiente potencia así:

maxPot=ULLONG_MAX/m;

Es evidente que si multiplico este valor por m obtendré el máximo valor que cabe en una variable de tipo unsigned long long. Ahora antes de calcular la potencia para la siguiente iteración comparo con este valor. Si el valor de la potencia actual es mayor que este valor no necesitamos calcular la siguiente potencia porque el valor va a ser más grande que el número de cajas puesto que va a ser mayor que el máximo ULLONG_MAX.
Así el bucle quedaría:

maxPot=ULLONG_MAX/m;
while (N>=v[n])  // how many keys we need
{
N-=v[n];  // boxes labeleds
if (v[n]>maxPot)
{
n++; break;  // too big, must be last one
}
else
{
v[n+1]=v[n]*m;  // variations
n++;
}
}

Y ahora el bucle final. Vamos calculando la división entre las potencias que hemos guardado y los restos restando el producto del cociente por el divisor. En cada iteración escribimos ya la letra de la etiqueta que hemos calculado. Al final del bucle el resto que nos quede es el índice de la última letra de la etiqueta.

while (--n>=0)  // calculate last label (with n+1 letters)
{
int nk=(int) (N/v[n]);
cout << L[nk];
N-=nk*v[n];
}
cout << L[N] << endl;

Y no hay nada más que hacer. Como siempre aquí está el fuente del programa completo y aquí el fichero de datos que me propusieron en el concurso.