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 (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:

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.

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 % 1.000.003.

Restricţii

• 1 ≤ N ≤ 1.000.000

Exemplu

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.

Cum se trimit solutii?