Inverseaza reviziile

Diferente pentru problema/arbnr intre reviziile #2 si #8

Diferente intre #1 si #2

Diferente intre titluri:

arbnr

Arbnr

Diferente intre continut:

== include(page="template/taskheader" task_id="arbnr") ==

Un arbore cu radacina este format dintr-o multime de noduri, dintre care un nod special denumit radacina. Fiecare nod are precizata o lista ordonata de noduri fiu, iar fiecare nod diferit de radacina este fiul al exact unui alt nod denumit parinte. Radacina nu are parinte.
Subarborele unui nod $X$ este un arbore cu radacina obtinut eliminand orice nod care nu este fiu direct sau indirect al nodului $X$ si considerand nodul $X$ radacina.
Fie doi arbori cu radacina {$A$}, $B$ cu radacinile $rA$ si respectiv {$rB$}. Fie {$a{~1~}a{~2~}a{~3~}...a{~k~}$} lista ordonata a fiilor lui {$rA$}, {$b{~1~}b{~2~}b{~3~}...b{~p~}$} lista ordonata a fiilor lui {$rB$}. Spunem ca arborii {$A$}, {$B$} sunt egali daca {$p=k$} si pentru orice {$1 ≤ i ≤ k$} subarborii cu radacinile {$a{~i~}$} si {$b{~i~}$} sunt egali.
Spunem ca arborele $A$ apare in arborele $B$ daca exista un nod {$nB$} din $B$ astfel incat subarborele cu radacina $nB$ este egal cu arborele {$A$}.

Un arbore cu radacina este format dintr-o multime de noduri, dintre care un nod special denumit radacina. Fiecare nod are precizata o lista ordonata de noduri fiu, iar fiecare nod diferit de radacina este fiul al exact unui alt nod denumit parinte. Radacina nu are parinte. Subarborele unui nod $X$ este un arbore cu radacina obtinut eliminand orice nod care nu este fiu direct sau indirect al nodului $X$ si considerand nodul $X$ radacina. Fie doi arbori cu radacina {$A$}, $B$ cu radacinile $rA$ si respectiv {$rB$}. Fie {$a{~1~}a{~2~}a{~3~}...a{~k~}$} lista ordonata a fiilor lui {$rA$}, {$b{~1~}b{~2~}b{~3~}...b{~p~}$} lista ordonata a fiilor lui {$rB$}. Spunem ca arborii {$A$}, {$B$} sunt egali daca {$p=k$} si pentru orice {$1 ≤ i ≤ k$} subarborii cu radacinile {$a{~i~}$} si {$b{~i~}$} sunt egali. Spunem ca arborele $A$ apare in arborele $B$ daca exista un nod {$nB$} din $B$ astfel incat subarborele cu radacina $nB$ este egal cu arborele {$A$}.
 

Gigel are o afacere cu o multime de $T$ arbori cu radacina (denumiti model) {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~T~}$}. Gigel vinde numai arbori cu radacina avand $N$ noduri in care nu apar nici unul dintre arborii model.
h2. Cerinta

* {$1 ≤ N ≤ 10.000$}
* {$0 ≤ T ≤ 40$}
* {$2 ≤ M ≤ 10.000$}

* {$30% din punctaj se acorda pentru N,M & le; 100 si T ≤ 10$}

* {$30% din punctaj se acorda pentru N,M ≤ 100 si T ≤ 10$}

* {$65% din punctaj se acorda pentru M ≤ 500$}
h2. Exemplu

|3
|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="arbnr") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

3795