Árbol de navidad
Es aceptado universalmente que para que un árbol de navidad se considere que está bien decorado, los ornamentos deben estar distribuidos correctamente por todas sus ramas. Esto tiene dos razones de ser: la primera es estética y la segunda de equilibrio. Si todos los adornos se concentran en la misma región del árbol, éste se caerá.
Algunos informáticos, además, solo admiten en casa árboles de navidad binarios. Esos árboles empiezan con un tronco que se divide en dos subárboles distintos. Cada uno de los dos subárboles puede a su vez, dividirse en otros dos subárboles más pequeños, etc., hasta que se llega a lo que podemos llamar hoja. Es en esas hojas donde se puede poner la decoración, colocando las famosas bolas de navidad o alguna otra figurita.
Como ejemplo, el árbol de la figura de la derecha tiene un tronco que se divide en dos subárboles. El de la izquierda termina directamente en una hoja, mientras que el de la derecha se divide a su vez en dos subárboles no divididos, uno de ellos con decoración y el otro sin ella.
Pues bien, se entiende que un árbol de navidad binario está decorado correctamente cuando en todos los sitios donde una rama (o el tronco) se divide en dos subárboles, el número de bolas de ambos no difiere en más de una unidad y, además, los dos subárboles están, vistos de forma individual, bien decorados. Con esta definición el árbol de la figura estaría bien decorado, mientras que si en la rama vacía hermana de la que tiene la bola colocáramos otra bola más, dejaría de estarlo.
Entrada
La entrada consta de una serie de árboles binarios de navidad, descritos cada uno en una línea que no superará los 100.000 caracteres. La línea contiene el recorrido en preorden del árbol binario. Más concretamente, cada carácter representa un nodo del árbol, ya sea interno o un nodo hoja. El carácter '*' indica la aparición de un adorno navideño (recuerda que sólo aparecen en las hojas), mientras que el carácter '.' representa una hoja sin adorno. Por su parte, el carácter 'Y' indica una división en el árbol, al que seguirá la descripción de los dos subárboles.
Salida
Para cada caso de prueba se mostrará una línea indicando si el árbol de navidad está correctamente decorado o si corre el riesgo de caerse. Si la decoración está bien colocada se escribirá OK, mientras que si no lo está, se escribirá KO.
Entrada de ejemplo
Y.Y*. Y.Y** *
Salida de ejemplo
OK KO OK