Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mergesort.in, mergesort.out | Sursă | Algoritmiada 2013, Runda 2 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Gheorghe •GheorgheMihai |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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 permutarea V si functia recursiva MergeSort(left, right care sorteaza sirul V pe intervalul (i,j). La inceput se apeleaza functia MergeSort(1,N) pentru a sorta tot vectorul. Functia MergeSort(left, right) functioneaza in felul urmator: se determina mijlocul intervalulul middle = (left + right) / 2 si se apeleaza pe rand functiile MergeSort(left, middle) si MergeSort(middle + 1, right), dupa care cele 2 siruri tocmai sortate se interclaseaza obtinandu-se sirul sortat intre pozitiile left si right.
Programul ruleaza in felul urmator:
void mergesort(int left, int right) {
if (left == right)
return;
int middle = (left + right) / 2;
mergesort(left, middle);
mergesort(middle + 1, right);
//interclaseaza cele 2 siruri de la left la middle, si de la middle + 1 la right
}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 ≤ 1.000.000
Exemplu
| mergesort.in | mergesort.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.
