Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | avd.in, avd.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
AVD
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
AVD
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=n1n2...+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] <= 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.
Cerinta
Dandu-se un arbore cu N noduri, calculati gradul AVD al acestuia.
Date de Intrare
Prima linie a fisierului de intrare avd.in contine T, numarul de teste din fisier apoi vor urma cele T teste. Pe prima linie a fiecarui test se afla N numarul de noduri, urmand apoi N-1 linii continand cate doua numere x, y cu semnificatia exista muchie intre nodurile x si y.
Date de Iesire
In fisierul avd.out vor exista T linii fiecare continand gradul AVD al arborelui descris la testului respectiv.
Restrictii si precizari
. 1 <= N <= 13
. 1 <= T <= 50
. rezultatul se va afisa cu 5 zecimale (prin rotunjire)
Exemplu
avd.in | avd.out |
3 | 0.80000 |
4 | 1.00000 |
1 2 | 1.00000 |
1 3 | |
1 4 | |
5 | |
1 2 | |
2 3 | |
3 4 | |
4 5 | |
1 |
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.