Fişierul intrare/ieşire:	sortare.in, sortare.out	Sursă	preONI 2008, Runda finala
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	0.1 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Sortare

Sortarea rapida (sau QuickSort) este un bine cunoscut algoritm de sortare. Algortimul functioneaza astfel:

• Se alege un element din sir, care se va numit pivot
• Se reordoneaza sirul astfel incat toate elementele care detin o valoare mai mica decat valoarea elementului pivot se vor pozitiona inaintea elementului pivot, si elementele care au o valoare mai mare decat valoarea elementului pivot se vor pozitiona dupa elementul pivot
• Se sorteaza recursiv cele doua bucati din sir

Cazul de baza a unei recursivitati sunt listele de dimensiune 0 sau 1. Putem implementa in pseudocod acest algoritm astfel:

function qsort(sir[])
   var stanga[], dreapta[], pivot
   if lungime(sir) <= 1
       return sir
   pivot = un element din sir
   for each x in sir
       if x < pivot then insereaza x in stanga
       if x > pivot then insereaza x in dreapta
   return concatenaeza(qsort(stanga), pivot, qsort(dreapta))

Fumeanu a implementat acest algoritm si considera ca implementarea lui este foarte eficienta. Nargy este mai intelept si isi da seama ca performanta intregului algoritm depinde de modul in care se selecteaza pivotul. Metoda folosita de Fumeanu este urmatoarea: pentru un sir de lungime i el alege mediana elementelor de pe pozitiile A_i, B_i si C_i (mediana reprezinta elementul mijlociu ca marime dintre cele 3).
Ajutati-l pe Nargy sa gaseasca o permutare a numerelor de la 1 la N pentru care implementarea lui Fumeanu are adancimea recursivitatii maxima.

Date de intrare

Fisierul de intrare sortare.in contine pe prima linie numarul N. Pe urmatoarele N-1 linii se vor gasi cate 3 numere natural A_i B_i C_i separate prin spatii (2≤i≤N).

Date de iesire

In fisierul de iesire sortare.out se va scrie pe prima linie HMax reprezentand adancimea maxima a recursivitatii. Pe urmatoarea linie se vor scrie N numere naturale reprezentand o permutare a numerelor de la 1 la N pentru care se obtine aceasta adancime.

Restrictii

• 1 ≤ N ≤ 5.000
• 1 ≤ A_i,B_i,C_i ≤ i
• Pozitiile din sir sunt numerotate incepand cu 1
• Daca exista mai multe solutii se poate afisa oricare

Exemplu

Explicatie

Pentru permutarea 1 2 3 4 5 recursivitatea are 3 nivele, astfel:

Elementele ingrosate sunt cele care sunt folosite in determinarea pivotului, iar cele subliniate reprezinta pivotul. Nu exista nici o permutare de lungime 5 care sa produca o adancime mai mare pentru datele de intrare date.

Cum se trimit solutii?