arbore2

Arbore2

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

In fisierul $arbori.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.

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

|
== include(page="template/taskfooter" task_id="arbore2") ==

 
== SmfTopic(topic_id="...") ==

1804