arbore2

Arbore2

== 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$ ( $0<=K<=100$ ) 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. Cerinta

h2. Date de intrare

Fisierul $arbori.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$.

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. Date de iesire

 
 
h2. Restrictii
 
* $... ≤ ... ≤ ...$

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="...") ==

1804