== include(page="template/taskheader" task_id="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):
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 $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$ flori fiecare, avand aceleasi radacini cu arborii initiali. Pentru a-mi atinge scopul pot sa fac $2$ tipuri de operatii:
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.
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.
h2. Date de intrare
h2. Cerinta
...
Scrieti un program care sa ma ajute!
h2. Date de iesire
h2. 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$.
h2. Restrictii
h2. 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.
h2. Exemplu
table(example). |_. arbore2.in |_. arbore2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
3
5 2 3
2 0 0
1 0 0
3
6 2 0
6 0 3
5 0 0
| 2 5
1 3
2 3
2 1
2 2
2 2
2 2
2 2
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="arbore2") ==
== SmfTopic(topic_id="...") ==
