ACM 2015 - Round #1Ended |
Un árbol es una estructura de datos ampliamente utilizada en la computación para modelar datos. Los arboles están formados por nodos que se conectan entre si utilizando aristas . En un árbol puede seleccionarse un nodo e identificarlo como el nodo raíz . A partir de este nodo se define una relación de parentesco de cada nodo con sus vecinos donde la raíz es padre de los nodos a los que esta conectado y estos a su vez son padre de sus vecinos (sin incluir a su padre). Un árbol binario cumple que todos sus nodos tienen a lo sumo 2 hijos, y se establece un orden entre ellos de forma tal que se les identifica como subárbol izquierdo y subárbol derecho.
Nuestro amigo Fito tomo un árbol binario y asignó ciertos valores a sus hojas, al terminar se dio cuenta de que estaba equilibrado . Esto significa que para todo nodo que no es hoja, la suma de los valores de las hojas de su subárbol izquierdo es igual a la suma de los valores de las hojas de su subárbol derecho.
Como de costumbre Fito se puso a jugar con el árbol y ahora nosotros tenemos que arreglar su desastre. Fito tomó en orden de izquierda a derecha los valores de las hojas del árbol anterior y los puso en una lista. Luego insertó en esta lista otros valores tratando de esconder su descubrimiento, tanto que ahora ni él mismo puede encontrarlo y está pidiendo nuestra ayuda.
Para cada caso se debe imprimir en una línea la mayor cantidad de hojas que pudo haber tenido el árbol de Fito.