== include(page="template/taskheader" task_id="mergesort") ==
Poveste şi cerinţă...
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 $(left, right)$. 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:
==code(cpp) |
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(left, right)$, iar sirul de la $left$ la $right$ este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia $MergeSort(left, right)$, aceasta sa continue doar daca sirul intre $left$ si $right$ *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 % 1.000.003$ dupa apelarea functiei $MergeSort(1, N)$ pe toate permutările de ordin $N$.
h2. Date de intrare
Fişierul de intrare $mergesort.in$ ...
Fişierul de intrare $mergesort.in$ va contine pe prima linie un numar natural $N$.
h2. Date de ieşire
În fişierul de ieşire $mergesort.out$ ...
Fişierul de ieşire $mergesort.out$ va contine pe prima linie un numar natural ce reprezinta $SOL % 1.000.003$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000.000$
h2. Exemplu
table(example). |_. mergesort.in |_. mergesort.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
| 4
|
h3. 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$.
== include(page="template/taskfooter" task_id="mergesort") ==
