Page 103 - MATINF Nr. 6

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 103

Exemplu

lant.in lant.out Explicat , ie
4 5 4 3 2 1 Pot exista mai multe lant , uri cu proprietatea
3 4 din enunt , , dar se va afis , a doar unul dintre ele.
1 2
1 4
2 4
2 3
Doru Constantin, Pites , ti

I 90 (arbore). Se d˘a un arbore cu n noduri prin vectorul tat˘a. Verificat , i dac˘a arborele este
ˆ
binar sau nu. In caz afirmativ se cere determinarea vectorilor stˆanga – dreapta construit , i dup˘a
regulile:

• dac˘a un nod k are doi fii i s , i j cu i < j, atunci i este fiu stˆang, iar j este fiu drept;

• dac˘a un nod k are un singur fiu i, atunci i este fiu stˆang, dac˘a i este impar s , i i este fiu
drept dac˘a i este par.

Cerint , ˘a
Cunoscˆand n s , i componentele vectorului tat˘a, afis , at , i DA, dac˘a arborele este binar, respectiv
NU contrar pe prima linie. Dac˘a arborele este binar, atunci pe a doua linie se va scrie vectorul
stˆanga, iar pe linia a doua vectorul dreapta.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 1000
Date de intrare

Fis , ierul arbore.in cont , ine pe prima linie n s , i pe linia a doua vectorul tat˘a.

Date de ies , ire

Fis , ierul de ies , ire arbore.out va cont , ine pe prima linie DA sau NU cu semnificat , ia din
enunt , . Dac˘a arborele este binar, atunci pe a doua linie se va scrie vectorul stˆanga, iar pe linia a
doua vectorul dreapta.

Exemplu

arbore.in arbore.out Explicat , ie
4 5 DA R˘ad˘acina arborelui este 0
2 0 2 3 0 1 0 0 s , i orice nod are cel mult doi fii.
5 0 3 4 0
2 0 2 5 2 NU
2 4
2 3

Doru Anastasiu Popescu, Pites , ti