Obi 2007 Nível2 Fase1 - Mobile

Autor da análise: gustpggustpg

http://olimpiada.ic.unicamp.br/passadas/OBI2007/res_fase1_prog/programacao_n2/pdf/provas/ProvaOBI2007_prog_f1n2.pdf

Resumo

No problema é definido um móbile (brinquedo infantil facilmente modelado com uma árvore) balanceado: Um móbile balanceado é aquele que dado um nó do mesmo, os filhos tem peso igual. O peso é definido como o número de nós, contando a raiz.

Solução

A solução fica simples com a implementação de uma função recursiva que retorna o peso do nó, caso seja verificado que o nó já não é balanceado, deve-se retornar um indicador (por exemplo -1, um valor impossível para "peso"). A função soma todos os pesos (chamando a ela mesma para cada filho do nó atual) e adiciona 1 (peso do próprio nó) caso seja retornado o indicador de desbalanceamento ou pesos diferentes, ela retorna o indicador.
Lembrando que o número de arestas é o número de nodos menos 1.

Testes

Entrada

9
1 0
2 0
3 0
4 1
5 1
6 2
7 2
8 3
9 8

Saída

bem

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License