Apilando panqueques

De fondo

Pilas y Colas son consideradas el material básico de las estructuras de datos y encuentran su uso en arquitectura, análisis gramático, sistemas operativos y simulación. Las pilas son también muy importantes en la teoría de lenguajes formales.

Este problema involucra tanto colocar mantequilla y sustento a la forma de los panqueques además de un delicado servidor que lanza panqueques según un único, pero completo conjunto de reglas.

El problema

Dada una pila de panqueques, escribe un programa que indique como debe ser ordenada la pila a fin de que el panqueque más grande este en el fondo y el panqueque más pequeño en la parte superior. El tamaño de los panqueques esta dado por el diámetro de los panqueques. Todos los panqueques en la pila tienen diferentes diámetros.

La ordenación de una pila esta dada por una serie de lanzadas de los panqueques al aire. Una lanzada consiste de insertar una espatula en medio de dos panqueques en la pila y lanzar (invertir) los panqueques con la espátula (poniendo al revés la sub-pila). Una lanzada esta especificada suministrando la posición del panqueque en el fondo de la sub-pila a ser lanzada. El panqueques en el fondo de la pila tiene la posición 1 y el panqueque en la parte de arriba de la pila la posición n.

Una pila esta especificada dados los diámetros de cada panqueque en el orden en el que los panqueques aparecen.

Por ejemplo, consideremos tres pilas de panqueques abajo (en el cual el panqueque 8 esta en la parte de arriba de la pila de la izquierda.

         8           7           2
         4           6           5
         6           4           8
         7           8           4
         5           5           6
         2           2           7
La pila de la izquierda puede ser transformada a la pila del centro via lanzada(3). La pila del centro puede ser transformada en la pila de la derecha via el comando lanzada(1).

La entrada

La entrada consiste de una secuencia de pila de panqueques. Cada pila puede tener de 1 a 30 panqueques y cada panqueque puede tener un diámetro entero comprendido entre 1 y 100. La entrada termina con fin de archivo. Cada pila esta dada en una sola línea de la entrada donde la parte de arriba de la pila aparece primero en una línea, el panqueque del fondo aparece al último y todos los panqueques están separados por un espacio.

La salida

Para cada pila de panqueques, se debe imprimir la pila original en una línea, seguido por alguna secuencia de lanzadas que resulta en una pila de panqueques ordenados donde el panqueque de mayor diámetro este en el fondo y el panque de menor diámetro esta en la parte de arriba. Para cada pila la secuencia de lanzadas debe terminar con un cero (que indica que no hacen falta más lanzadas). Una vez ordenada no se deben hacer más lanzadas.

Ejemplo de entrada

1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

Ejemplo de salida

1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0