Pagini recente » Banana | Diferente pentru problema/asi intre reviziile 26 si 38 | Autentificare | Diferente pentru problema/asi intre reviziile 29 si 38 | arbori3

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2022-03-13 13:31:58.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	arbori3.in, arbori3.out	Sursă	ad-hoc
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Permutări de traversare a arborilor

Se dă un arbore având $n$ noduri numerotate $1, 2, \ldots, n$ ale cărui $n-1$ arce au ataşate ca lungimi numere întregi. Se consideră cele $n!$ permutări ale elementelor mulţimii $\lbrace 1, 2, \ldots, n \rbrace$ notate cu $P_i$ , unde $1 \leq i \leq n!$ . De asemenea notăm cu $P_{i,j}$ al $j$ -lea element al mulţimii $P_i$ ( $1 \leq j \leq n$ ).

Fiecare permutare $P_i$ reprezintă o traversare a secvenţei de noduri ale arborelui ceea ce înseamnă că ne deplasăm de la nodul $P_{i,1}$ la nodul $P_{i,2}$ pe drumul cel mai scurt, pe urmă de la nodul $P_{i,2}$ la nodul $P_{i,3}$ tot pe drumul cel mai scurt şi tot aşa până la nodul $P_{i,n}$ . Notăm distanţa totală a traversării date de permutarea $P_i$ cu $D(P_i)$ .