Pagini recente » Cod sursa (job #758910) | Borderou de evaluare (job #594458) | Cod sursa (job #2205785) | Rezultatele filtrării | Diferente pentru problema/avele intre reviziile 3 si 2
Diferente pentru
problema/avele intre reviziile
#3 si
#2
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="avele") ==
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$).
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. Cerinţă
Se dă un *arbore binar* cu rădăcina în nodul 1. Să determine costul minim pentru a-l transforma într-un arbore *AVELE*. Operaţiile posibile sunt:
* Ştergerea unei frunze de oriunde din arbore (cu costul $cost_rem$);
* Adăugarea unei frunze oriunde în arbore (cu costul $cost_add$).
*Înălţimea* subarborelui cu rădăcina în nodul $v$ este egală cu $0$, dacă şi numai dacă subarborele este vid ($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$, 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.
Fişierul de intrare $avele.in$ ...
h2. Date de ieşire
h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $0 ≤ left_son(i), right_son(i) ≤ N$
* $1 ≤ cost_add, cost_rem ≤ 1.000.000.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. avele.in |_. avele.out |
| 3 10 5
2 0
3 0
0 0
| 5
|
| 3 2 8
0 2
3 0
0 0
| 2
|
| 3 1 1
2 3
0 0
0 0
| 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="avele") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.