Visita a Sydney


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal

El pequeño Lucas ha realizado una visita turística a un pueblo cercano a Sydney, una ciudad de Australia. Da la casualidad de que la disposición de las calles en el pueblo parece terriblemente familiar a la forma de un árbol binario perfecto de orden K. Un árbol binario perfecto de orden K consta de 2^K - 1 nodos dispuestos en K niveles (al igual que en la imagen). Cada nodo contiene un edificio etiquetado con un número de casa. Además, todos los edificios excepto los del último nivel tienen un hijo izquierdo y uno derecho (ver la imagen de nuevo).

Descripcion

Lucas visitó todos los edificios del pueblo y anotó el orden exacto de entrada. Ahora quiere describirte cómo es el pueblo, pero no puede recordarlo bien. Por suerte, recuerda la forma en que visitó los edificios:

  1. Al principio, estaba parado frente al único edificio en el primer nivel.

  2. Si el edificio frente al que se encuentra actualmente tiene un hijo izquierdo que aún no ha visitado, se moverá frente al hijo izquierdo.

  3. Si el edificio no tiene un hijo izquierdo o ya lo visitó, ingresará al edificio actual y escribirá el número de su casa en su papel.

  4. Si ya ha visitado el edificio actual y el edificio tiene un hijo derecho, se moverá frente al hijo derecho.

  5. Si ha visitado el edificio actual y su hijo izquierdo y derecho, volverá al padre del edificio actual.

Después de visitar los pueblos de las imágenes de arriba, el papel se vería así: 213 para el primer pueblo y 1643527 para el segundo pueblo. Escriba un programa para ayudar a Lucas a reconstruir el orden de los números de las casas en cada nivel.

Entrada

La primera línea de entrada contiene el número entero K (1 \leq K \leq 10), el número de niveles del pueblo que acaba de visitar Lucas. La segunda línea de entrada contiene 2^K - 1 enteros, la secuencia de números de casas en el papel de Lucas. Los números de las casas serán únicos y del intervalo [1, 2^K - 1].

Salida

La salida debe constar de K líneas. La i-ésima línea debe contener la secuencia de números de casas en el i-ésimo nivel del pueblo.

Ejemplo de Entrada

3
1 6 4 3 5 2 7

Ejemplo de Salida

3
6 2
1 4 5 7

Comments

There are no comments at the moment.