Diferente pentru problema/arbfind intre reviziile #3 si #35

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/taskheader" task_id="arbfind")==
==Include(page="template/raw")==
Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si $A{~1~}, A{~2~}, ..., A{~n~}$ (unde $n ≥ 0$) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore $A{~i~}$ este denumit fiu al radacinii arborelui si este conectat printr-o muchie de radacina arborelui.
Se numeste arbore cu radacina o structura care contine un nod special denumit radacina arborelui si $A ~1~, A ~2~, ..., A ~n~$ (unde $n &me; 0$) arbori cu radacina (denumiti subarbori ai radacinii). Nodul radacina al fiecarui arbore A[i] este denumit fiu al radacinii arborelui si este conectat printr-o muchie de radacina arborelui.
 
Doi arbori cu radacina sunt identici daca radacinile celor doi au acelasi numar de subarbori si acestia sunt identici (mai exact, pentru orice i=1, 2, ..., n subarborele i al primului este identic cu subarborele i al celui de-al doilea).
Doi arbori cu radacina sunt identici daca radacinile celor doi au acelasi numar de subarbori si acestia sunt identici (mai exact, pentru orice $i=1, 2, ..., n$ subarborele $i$ al primului este identic cu subarborele $i$ al celui de-al doilea).
O termita poate "ciopli" un arbore actionand astfel:
1. termita porneste de la radacina arborelui;
2. la fiecare moment (in orice nod s-ar afla), termita poate face una dintre urmatoarele operatii:
1) termita porneste de la radacina arborelui;
 
2) la fiecare moment (in orice nod s-ar afla), termita poate face una dintre urmatoarele operatii:
 
- sta in nod si mananca cea mai din dreapta muchie, eliminand astfel cel mai din dreapta fiu si subarborele corespunzator (acestea cad si vor fi mancate de alte termite lenese);
 
- inainteaza pe muchia din dreapta, spre fiul ramas cel mai din dreapta al nodului in care se afla;
 
- se opreste
* sta in nod si mananca cea mai din dreapta muchie, eliminand astfel cel mai din dreapta fiu si subarborele corespunzator (acestea cad si vor fi mancate de alte termite lenese);
* inainteaza pe muchia din dreapta, spre fiul ramas cel mai din dreapta al nodului in care se afla;
* se opreste
Doua termite prietene aleg doi arbori si ii cioplesc in modul descris pana cand obtin doi arbori identici. Similaritatea dintre doi arbori este egala cu numarul maxim de noduri care raman in fiecare dintre cei doi arbori identici obtinuti prin cioplire.
h2. Date de Intrare
Pe prima linie a fisierului de intrare arbfind.in se gaseste un numar natural N reprezentand numarul de noduri din arborele model, nodurile fiind numerotate de la 1 la N. Pe liniile 2..N+1 se va afla descrierea arborelui model. Mai exact, pe linia i se va afla un numar natural F[i-1] reprezentand numarul de fii directi ai nodului i-1, urmat de F[i-1] numere naturale cuprinse intre 1 si N, reprezentand in ordinea de la stanga la dreapta fiii nodului i-1.
Pe prima linie a fisierului de intrare $arbfind.in$ se gaseste un numar natural $N$ reprezentand numarul de noduri din arborele model, nodurile fiind numerotate de la $1$ la $N$. Pe liniile $2..N+1$ se va afla descrierea arborelui model. Mai exact, pe linia $i$ se va afla un numar natural $F{~i-1~}$ reprezentand numarul de fii directi ai nodului $i-1$, urmat de $F ~i-1~$ numere naturale cuprinse intre $1$ si $N$, reprezentand in ordinea de la stanga la dreapta fiii nodului $i-1$.
Linia N+2 va contine un numar natural M reprezentand numarul de noduri din arborele de evaluat. Liniile N+3..N+M+2 vor contine descrierea arborelui de evaluat, in mod analog cu descrierea arborelui model.
Linia $N+2$ va contine un numar natural $M$ reprezentand numarul de noduri din arborele de evaluat. Liniile $N+3..N+M+2$ vor contine descrierea arborelui de evaluat, in mod analog cu descrierea arborelui model.
h2. Date de Iesire
Fisierul de iesire arbfind.out va contine M linii. Pe linia i se va afla similaritatea subarborelui cu radacina in nodul i fata de arborele model.
Fisierul de iesire $arbfind.out$ va contine $M$ linii. Pe linia $i$ se va afla similaritatea subarborelui cu radacina in nodul $i$ fata de arborele model.
h2. Restrictii si precizari
Radacina arborilor este intotdeauna nodul 1.
 
1 <= M, N <= 32000
* Radacina arborilor este intotdeauna nodul $1$.
* $1 &le; M, N &le; 32000$
h2. Exemplu
table(example). |_. arbfind.in |_. arbfind.out |
| 4
2 2 3
1 4
0
0
9
2 2 3
2 4 5
2 6 7
1 8
0
0
1 9
0
0
| 3
4
2
2
1
1
2
1
1
|
 
h3. Explicatii
|arbfind.in |arbfind.out |Arbore model Arbore de evaluat |
!problema/arbfind?arbfind.jpg!
|4 |3 | |
| | | |
|2 2 3 |4 | |
| | | |
|1 4 |2 |De exemplu, pentru nodul 1 din arborele model s-au eliminat in ordine subarborii cu radacinile 3, 5 si 8. Din arborele model se elimina subarborele cu radacina 3. |
| | | |
|0 |2 | |
| | | |
|0 |1 | |
| | | |
|9 |1 | |
| | | |
|2 2 3 |2 | |
| | | |
|2 4 5 |1 | |
| | | |
|2 6 7 |1 | |
| | | |
|1 8 | | |
| | | |
|0 | | |
| | | |
|0 | | |
| | | |
|1 9 | | |
| | | |
|0 | | |
| | | |
|0 | | |
De exemplu, pentru nodul 1 din arborele model s-au eliminat in ordine subarborii cu radacinile 3, 5 si 8. Din arborele model se elimina subarborele cu radacina 3.
==Include(page="template/taskfooter" task_id="arbfind")==
==Include(page="template/taskfooter" task_id="arbfind")==
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1103