Árboles recursivos P14094
El planeta de Escheria es universalmente conocido por sus inmensos bosques de árboles recursivos. Para los que nunca hayáis tenido la suerte de visitar este planeta, un árbol recursivo se define de la siguiente manera: tiene un tronco, como todo árbol, y su copa está formada por una estructura que se repite a diferentes escalas. Veamos un ejemplo, una de las especies más útiles es el árbol D.
La empresa D-Wood utiliza este árbol para la producción de madera, el hecho de que su copa sea infinitamente grande rentabiliza mucho el negocio pero añade una seria dificultad, cómo empaquetar la madera. La solución, premio nobel de economía, es demasiado complicada para explicarla aquí pero incluye numerar los nodos de abajo a arriba y de izquierda a derecha y necesita saber en todo momento cuál es el padre de cada nodo. Después de numerar el árbol, éste quedaría así:
Has sido contratado por la empresa D-wood y tienes que crear un programa que dado el número de un nodo diga cuál es el de su padre.
Entrada
La entrada comienza con un natural N, que es el número de consultas, 1 ≤ N ≤ 20000. Siguen N líneas, cada una con un número natural C, que es el número de un nodo de nuestro árbol D.
Salida
La salida tiene que contener para cada consulta el número del padre del nodo C, siguiendo el formato del ejemplo.
Puntuación
- TestP: Casos donde 1 ≤ C ≤ 20000. 50 Puntos
- TestG: Casos donde 1 ≤ C ≤ 1015. 50 Puntos
Input
3 2 1 8
Output
El padre del 3 es el 2. El padre del 2 es el 1. El padre del 1 es la tierra. El padre del 8 es el 5.
- Author
- Alex Alvarez y Xavier Spagnolo
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++