Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-01-08 20:37:44.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:mergesort.in, mergesort.outSursăAlgoritmiada 2013, Runda 2
AutorMihai CalanceaAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mergesort

Marele Intelept a venit sa va explice algoritmul MergeSort. Algoritmul MergeSort este folosit pentru a sorta siruri. Acesta functioneaza in felul urmator: Fie functia recursiva MergeSort(i,j) care sorteaza sirul pe intervalul (i,j). La inceput se apeleaza functia MergeSort(1,n) pentru a sorta tot vectorul. Functia MergeSort(i,j) functioneaza in felul urmator: se determina mijlocul intervalulul mij = (i + j) / 2 si se apeleaza pe rand functiile MergeSort(i,mij) si MergeSort(mij + 1, j), dupa care cele 2 siruri tocmai sortate se interclaseaza obtinandu-se sirul sortat intre pozitiile i si j.

O calance a aprofundat acest algoritm si s-a decis sa faca urmatoarea optimizare: daca se apeleaza functia MergeSort(i,j), iar sirul de la i la j este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia MergeSort(i,j), aceasta sa continuie doar daca sirul NU este sortat.

Stiind ca la fiecare apelare a functiei MergeSort aceasta incrementeaza cu +1 valoarea unui numar natural SOL care initial este 0, sa determine SOL % 666013 dupa apelarea functiei MergeSort(1,n) a tuturor permutarilor de ordin N.

Date de intrare

Fişierul de intrare mergesort.in va contine pe prima linie un numar natural N.

Date de ieşire

Fişierul de ieşire mergesort.out va contine pe prima linie un numar natural ce reprezinta SOL % 666013.

Restricţii

  • 1 ≤ N ≤ 100.000

Exemplu

mergesort.inmergesort.out
2
4

Explicaţie

Pentru permutarea (1,2) apelam MergeSort(1,2) si ne oprim. SOL = 1.
Pentru permutarea (2,1) apelam MergeSort(2,1). SOL devine 2. Cum sirul nu este sortat continuam. Apelam MergeSort(1,1) si MergeSort(2,2) si am sortat sirul. In final SOL devine 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?