Arbres aixafats P19515


Statement
 

pdf   zip

thehtml

Donat un arbre general, sigui t la seva talla (el seu nombre d’elements), i sigui a la seva alçada. El quocient t/a és una mesura de com d’“aixafat” està l’arbre.

(Per veure alguns exemples, consulteu la versió pdf o ps d’aquest enunciat.)

Feu un programa que llegeixi la forma de diversos arbres generals, i que per a cadascun escrigui el màxim quocient t/a de tots els seus subarbres.

Entrada

L’entrada comença amb m, el nombre d’arbres que cal tractar. Segueix la descripció dels m ‍arbres segons s’explica a l’exercici , amb dues excepcions: D’una banda, no es donen els valors, perquè el contingut dels nodes aquí no és important. De l’altra, tampoc no es dóna el nombre de nodes, ja que no cal guardar els arbres a cap vector per resoldre aquest exercici.

Sortida

Escriviu amb tres decimals el màxim quocient t/a dels subarbres de cada arbre donat.

Public test cases
  • Input

    3
    
    3 2 0 1 1 0 0 4 0 0 0 0
    2 1 0 0
    2 0 0
    

    Output

    2.500
    1.333
    1.500
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++