Fişierul intrare/ieşire:	arbore2.in, arbore2.out	Sursă	Stelele Informaticii 2003, clasele 11-12
Autor	Mihai Stroe	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arbore2

Am doi copaci, reprezentati prin doi arbori binari cu M, respectiv N noduri. In fiecare nod al unui astfel de arbore cresc flori (cel putin 0, cel mult 10). Ordinea fiilor conteaza (se face distinctie intre fiul stang si fiul drept). Doi arbori binari cu flori in noduri sunt similari daca (definitie recursiva):

• au ambii 0 noduri SAU
• au ambii cel putin un nod, acelasi numar de flori in radacina, subarborii stangi sunt similari si subarborii drepti sunt similari.

Vreau sa transform cei doi arbori dati in 2 arbori similari (conform definitiei de mai sus) cu exact K (0 ≤ K ≤ 100) flori fiecare, avand aceleasi radacini cu arborii initiali. Pentru a-mi atinge scopul pot sa fac 2 tipuri de operatii:

• tai o craca (elimin un subarbore dintr-unul din cei doi arbori)
• rup o floare (scad cu 1 numarul de flori din unul din nodurile unuia din arbori)

Deoarece vreau sa muncesc cat mai putin pentru a-mi atinge scopul, doresc sa tai cat mai putine craci si, daca am mai multe variante de a taia cat mai putine craci, sa aleg una in care sa rup cat mai putine flori.

Cerinta

Scrieti un program care sa ma ajute!

Date de intrare

Fisierul arbore2.in contine pe prima linie numarul K de flori dorit. Urmeaza cei 2 arbori, unul dupa altul. Un arbore se da prin numarul de noduri NR (1 ≤ NR ≤ 100). Urmeaza NR linii, fiecare continand informatia pentru un nod: numarul de flori F (0 ≤ F ≤ 10), numarul fiului stang (sau 0 daca acesta nu exista) si numarul fiului drept (sau 0 daca acesta nu exista). Arborii sunt valizi (contin numerele de la 1 la NR, nu au cicluri etc.) si au amandoi radacina in nodul 1.

Date de iesire

In fisierul arbore2.out veti afisa pe prima linie numarul T de taieri de craci si numarul R de ruperi de flori din solutia optima. Pe urmatoarele T linii veti afisa taierile de craci. Taierea unei craci se da prin doua numere ARB si NOD; asta inseamna ca am taiat craca din arborele ARB (1 sau 2), care lega nodul NOD de tatal lui. Pe urmatoarele R linii veti afisa ruperile de flori. Ruperea unei flori se da prin doua numere ARB si NOD; asta inseamna ca am rupt o floare din nodul NOD al arborelui ARB. Numerele de pe fiecare linie se vor separa printr-un spatiu. Daca exista mai multe solutii optime, afisati una oarecare. Toate testele date vor avea cel putin o solutie.

Exemplu

Cum se trimit solutii?