Sistema de numeración factorial
Los sistemas de numeración son todo un mundo. Estamos tan habituados a la notación decimal (y algunos también a la binaria) que no la valoramos. Un buen ejercicio para hacerlo es, sin duda, intentar sumar números romanos.
La notación decimal, igual que la binaria o la hexadecimal, pertenece a la "familia" de notaciones posicionales: el valor de un dígito se multiplica por un factor que depende de la posición que ocupa en el número completo. Se ve bien con un ejemplo: en el número 444 cada uno de los guarismos "4" aportan una cantidad distinta a la cifra final. En concreto el factor que multiplica al número más a la derecha es el 1 y este factor se va multiplicando por 10 según vamos hacia la izquierda.
Este tipo de numeración en el que los factores se van multiplicando por un valor fijo son los más habituales. Así funciona la notación decimal (base 10), el sistema binario (base 2) y el hexadecimal (base 16), por ejemplo. Hay, no obstante, otros sistemas de numeración cuya base es una mezcla y el factor no es multiplicado siempre por el mismo valor. A quien le sorprenda esto que piense en la forma en la que medimos el tiempo. La Tierra, por ejemplo, tarda 52 semanas, 1 día, 6 horas, 9 minutos, 9 segundos y 733 milisegundos en dar la vuelta al Sol. Pensándolo bajo el prisma de los sistemas de numeración, ese "número" está formado por los "dígitos" 52 1 6 9 9 733 y se mezclan la base 7, 24, 60 y 1000 dependiendo de la posición.
Otro sistema de numeración de base mixta es el sistema de numeración factorial (también conocido como factorádico). En él el dígito menos significativo está en base 0!, el siguiente en 1! y le siguen el 2!, 3!, etc.
A modo de ejemplo, en este sistema el número 2.3.0.1.1.0 (separando los dígitos con puntos pues para números más grandes cada "dígito" podría requerir más de un guarismo) sería en decimal equivalente a:
2.3.0.1.1.0 = 2 × 5! + 3 × 4! + 0 × 3! + 1 × 2! + 1 × 1! + 0 × 0! = 315
Lo bueno de este sistema de numeración es que permite expresar números muy grandes con pocos dígitos. Y si en algún sitio salen números grandes, es cuando contamos la cantidad de permutaciones de un conjunto de objetos.
Dado un número de N dígitos en factorádico, ¿a qué permutación de los elementos entre 1 y N representa si las ponemos una detrás de otra en orden?
Entrada
La entrada comienza por un número indicando la cantidad de casos de prueba que hay que procesar.
Cada caso de prueba está compuesto por dos líneas. En la primera aparece únicamente la cantidad N de cifras que tiene el número factorádico que aparece en la fila siguiente (1 ≤ N ≤ 300.000). Cada uno de los "dígitos" de esa segunda línea estarán separados por espacios*.
Se garantiza que el número es correcto: el dígito cuyo factor multiplicativo es k! estará entre 0 y k. Además, por comodidad, siempre aparecerán las N cifras aún cuando las más significativas sean cero.
Salida
Por cada caso de prueba se escribirá una línea con la permutación de los números del 1 al N que ocupa esa posición si las colocamos en el orden natural de las secuencias de números. Ten en cuenta que la primera permutación es la 0.
Entrada de ejemplo
4 3 0 0 0 3 1 0 0 4 2 2 0 0 4 3 2 1 0
Salida de ejemplo
1 2 3 2 1 3 3 4 1 2 4 3 2 1
Notas
Las permutaciones de los elementos [1, 2, 3] ordenadas son:
| Posición | Permutación |
|---|---|
| 0 | 1 2 3 |
| 1 | 1 3 2 |
| 2 | 2 1 3 |
| 3 | 2 3 1 |
| 4 | 3 1 2 |
| 5 | 3 2 1 |
El primer caso de prueba del ejemplo es 0×2! + 0×1! + 0×0! = 0, por lo que la respuesta es 1 2 3.
El segundo caso, 1 0 0 representa el 1×2! + 0×1! + 0×0! = 2, que se corresponde con el 2 1 3.