==Include(page="template/taskheader" task_id="avd")==

==Include(page="template/raw")==
 
Un arbore este un graf neorientat, conex cu $N$ noduri si $N-1$ muchii. Se numeste arbore AVD un arbore care pentru fiecare partitie a lui $N  =n{~1~} + n{~2~} + ... + n{~k~}$ nodurile arborelui se pot imparti in $k$ multimi astfel incat multimea $i$ are n{~i~} noduri si fiecare multime ramane conexa, n{~i~} &le; n{~j~} pentru $i < j$. Gradul AVD al unui arbore este numarul de partitii care indeplinesc conditiile anterioare impartit la numarul total de partitii existente pentru $N$.

Un arbore este un graf neorientat, conex cu $N$ noduri si $N-1$ muchii. Se numeste arbore AVD un arbore care pentru fiecare partitie a lui $N  = n{~1~} + n{~2~} + ... + n{~k~}$ nodurile arborelui se pot imparti in $k$ multimi astfel incat multimea $i$ are n{~i~} noduri si fiecare multime ramane conexa, $n{~i~} &le; n{~j~}$ pentru $i < j$. Gradul AVD al unui arbore este numarul de partitii care indeplinesc conditiile anterioare impartit la numarul total de partitii existente pentru $N$.

h2. Cerinta

h2. Exemplu

table(example). |_. avd.in |_. avd.out | explicatii |

table(example). |_. avd.in |_. avd.out |

| 3
4
1 2

1
| 0.80000
1.00000

1.00000
| Pentru primul test, exista in total 5  partitii pentru 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4 din care doar partitia 2+2 nu poate fi obtinuta. Deci gradul AVD al arborelui este 4/5=0.80000. |

1.00000 |
 
h3. Explicatii
 
Pentru primul test, exista in total $5$ partitii pentru $4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4$ din care doar partitia $2+2$ nu poate fi obtinuta. Deci gradul AVD al arborelui este $4/5=0.80000$.

==Include(page="template/taskfooter" task_id="avd")==

1310