Arbres Verd-Blau P24958


Statement
 

pdf   zip

thehtml

Considerem arbres binaris on cada node pot tenir un color associat: verd o blau. Diem que un arbre binari amb colors és un arbre verd-blau quan compleix aquestes dues propietats:

  • Tot node verd té tots els seus fills blaus.
  • Tots els camins que van d’un node fins a qualsevol de les seves fulles té el mateix nombre de nodes blaus.

Donat un arbre verd-blau, diem que la seva alçada blava és el nombre de nodes blaus en els camins des de la seva rel fins a les seves fulles (com que l’arbre és verd-blau, aquest valor és únic).

Per exemple, l’arbre de la figura següent és un arbre verd-blau i la seva alçada blava és 3.

Entrada

L’entrada comença amb un natural n, el nombre d’arbres que cal tractar. Després apareix la descripció dels n arbres, corresponent al seu recorregut en preordre, amb els nodes verds marcats amb caràcters G, els nodes blaus marcats amb caràcters B i els arbres buits marcats amb guions.

Sortida

Per a cada arbre de l’entrada, si aquest és un arbre verd-blau, cal escriure la seva alçada blava. Altrament, cal escriure no.

Observació

Heu de crear l’arbre on la informació del color sigui explícita en el node, i vetllar per no tenir fuites de memòria.

Public test cases
  • Input

    6
    
    -
    B--
    G--
    BG--G--
    GB--G--
    BGBB--B--BB--B--BBG---BG--G--
    

    Output

    0
    1
    0
    1
    no
    3
    
  • Information
    Author
    Jordi Petit i Jordi Cortadella
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++