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

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="arbnr") ==
Poveste şi cerinţă...
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
 
Scrieti un program care sa calculeze cati arbori cu radacina cu $N$ noduri distincti poate vinde Gigel.
h2. Date de intrare
Fişierul de intrare $arbnr.in$ ...
Fisierul de intrare $arbnr.in$ contine pe prima linie numerele naturale $N$ si $T$ reprezentand numarul de noduri din arborii vanduti de Gigel si respectiv numarul de arbori model. In continuare urmeaza $T$ blocuri de date, fiecare bloc reprezentand descrierea unui arbore model. Blocul care descrie un arbore model contine pe prima linie un numar natural $M$ reprezentand numarul de noduri din arbore. Pe cea de a doua linie sunt scrise $M-1$ numere naturale separate prin spatiu. Al {$i$}-lea numar de pe linie este nodul parinte al nodului {$i+1$} ({$1 ≤ i ≤ M-1$}). Radacina este nodul cu numarul {$1$}. Ordinea fiilor este considerata ordinea crescatoare a numerelor lor de ordine.
h2. Date de ieşire
h2. Date de iesire
În fişierul de ieşire $arbnr.out$ ...
Fisierul $arbnr.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand numarul de arbori cu radacina distincti cu $N$ noduri in care nu apare nici unul dintre arborii model modulo {$9907$}.
h2. Restricţii
* $... ≤ ... ≤ ...$
* {$1 ≤ N ≤ 10.000$}
* {$0 ≤ T ≤ 40$}
* {$2 ≤ M ≤ 10.000$}
* {$30% din punctaj se acorda pentru N,M & le; 100 si T ≤ 10$}
* {$65% din punctaj se acorda pentru M ≤ 500$}
h2. Exemplu
table(example). |_. arbnr.in |_. arbnr.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|4 2
3
1 2
3
1 1
|3
|
h3. Explicaţie

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.