Pagini recente » Cod sursa (job #7104) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2886889) | Diferente pentru problema/avele intre reviziile 9 si 4
Diferente pentru
problema/avele intre reviziile
#9 si
#4
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="avele") ==
Un 'arbore':https://hollywoodp.wpengine.com/wp-content/uploads/2013/10/loan-oak-tree.jpg cu rădăcină $T$ se numeşte arbore *AVELE* dacă, pentru fiecare nod nenul $v$, avem că $v$ are exact doi fii (nu neapărat nenuli), $left_son(v)$ şi $right_son(v)$, iar _înălţimea subarborilor cu rădăcina în cei doi fii diferă cu maxim 1_. (formal, $|height(left_son(v)) - height(right_son(v))| <= 1$, unde $|x|$ denotă valoarea absolută a numărului întreg $x$).
Un arbore cu rădăcină $T$ se numeşte arbore *AVELE* dacă, pentru fiecare nod nenul $v$, avem că $v$ are exact doi fii (nu neapărat nenuli), $left_son(v)$ şi $right_son(v)$, iar _înălţimea subarborilor cu rădăcina în cei doi fii diferă cu maxim 1_. (formal, $|height(left_son(v)) - height(right_son(v))| <= 1$, unde $|x|$ denotă valoarea absolută a numărului întreg $x$).
*Înălţimea* subarborelui cu rădăcina în nodul $v$ este egală cu $0$, dacă şi numai dacă subarborele este vid (altfel spus, $height(0) = 0$), altfel se defineşte după formula $height(v) = 1 + max(height(left_son(v)), height(right_son(v)))$.
h2. Date de intrare
Fişierul de intrare $avele.in$ conţine pe prima linie numerele naturale $N, cost_add, cost_rem$ separate prin câte un spaţiu, iar pe următoarele $N$ linii, câte două numere naturale, reprezentând $left_son(i)$, respectiv $right_son(i)$, pentru fiecare nod $i$ din arbore.
Fişierul de intrare $avele.in$ conţine pe prima linie numerele naturale $N$, $cost_add$, $cost_rem$, iar pe următoarele două linii, câte două numere naturale,
reprezentând $left_son(i)$, respectiv $right_son(i)$, pentru fiecare nod $i$ din arbore.
h2. Date de ieşire
Fişierul de ieşire $avele.out$ trebuie să conţină un singur număr natural, reprezentând costul minim pentru a transforma arborele într-unul *AVELE*.
În fişierul de ieşire $avele.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $0 ≤ left_son(i), right_son(i) ≤ N$
* $1 ≤ cost_add, cost_rem ≤ 1.000.000.000$
* $Se garantează că datele de intrare sunt valide pentru un arbore binar cu rădăcina în nodul 1.$
h2. Exemplu
| 0
|
== include(page="template/taskfooter" task_id="avele") ==
== include(page="template/taskfooter" task_id="avele") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.