Jogurt P98569


Statement
 

pdf   zip

thehtml

Un arbol binario completo de N niveles es una estructura jerárquica de nodos, donde hay un nodo (el nodo raíz) que está en nivel 0 y que tiene exactamente dos nodos hijo, que están en nivel 1, y que a su vez cada uno de ellos tiene 2 nodos hijos, que están en nivel 2, etcétera, hasta llegar a un cierto nivel N, donde ningún nodo tiene nodos hijo.

Un arbol binario completo de N niveles tiene exactamente 2N−1 nodos. En este problema te pedimos que escribas los números del 1 al 2N−1 en los nodos de un árbol binario completo de N niveles, de modo que se cumpla la siguiente propiedad: para cada nodo de nivel D, el valor absoluto de la diferencia entre la suma de los números del subárbol izquierdo y la suma de los números del subárbol derecho es 2D.

Por ejemplo: para D=0, se debe cumplir que la suma del subárbol izquierdo del nodo raíz y la suma del subárbol derecho del nodo raíz tienen que diferir en exactamente 20=1. Para D=1, los respectivos subárboles deben diferir en 21=2.

Hay que usar cada número exactamente una vez. La solución no tiene porque ser única.

Entrada

La primera y única línea de la entrada contiene el entero N (1≤ N≤ 15).

Salida

Escribe los 2N−1 números separados por espacios en una única línea, en pre-orden: para escribir los números en pre-orden, debes escribir primero el número del nodo raíz, luego el subárbol de la izquierda (de nuevo, en pre-orden) y luego el subárbol de la derecha.

Public test cases
  • Input

    2
    

    Output

    1 2 3 
  • Input

    3
    

    Output

    1 3 4 6 2 5 7 
  • Information
    Author
    COCI06/07
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++