Fişierul intrare/ieşire:sortari2.in, sortari2.outSursăRMMS 2011 - Ziua 2
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sortari2

Micul Johny se relaxează sortând permutări. Astfel, el alege la întâmplare o permutare cu N elemente. Cât timp această permutare nu e sortată crescător, Johny alege două numere de pe poziţii consecutive în permutare şi le interschimbă. După un timp învaţă cum să sorteze orice permutare prin procedeul de mai sus cu număr minim de interschimbări.
După ce Johny îşi îmbunătăţeşte deprinderile algoritmice, în loc să interschimbe doar elemente de pe poziţii consecutive, el va putea interschimba oricare două elemente din permutare. Johny învaţă să sorteze permutările folosind un număr minim de astfel de operaţii.
Evident, pentru orice permutare numărul minim de operaţii prin care se realizează sortarea folosind al doilea procedeu e mai mic sau egal decât numarul minim de operaţii folosind primul procedeu.
Determinaţi câte permutări cu N elemente pot fi sortate mai rapid prin procedeul al doilea decât prin primul procedeu (cu număr optim de interschimbari mai mic). Deoarece răspunsul poate fi foarte mare, se va afişa doar restul împărţirii acestuia la 999017.

Date de intrare

Fişierul de intrare sortari2.in conţine pe prima linie numărul natural N, cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire sortari2.out va conţine o singură linie pe care se va afla restul împărţirii răspunsului la 999017.

Restricţii

  • 2 ≤ N ≤ 1000

Exemplu

sortari2.insortari2.out
411

Explicaţie

Sunt 11 permutări cu proprietatea cerută:
1 4 3 2
2 4 3 1
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
De exemplu, permutarea 4 2 1 3 poate fi sortată cu numar minim de paşi folosind primul procedeu astfel: 4 2 1 3 => 2 4 1 3 => 2 1 4 3 => 1 2 4 3 => 1 2 3 4. Au fost necesari 4 paşi. Folosind al doilea procedeu, permutarea poate fi sortată mai rapid astfel: 4 2 1 3 => 4 2 3 1 => 1 2 3 4. Au fost necesari doar 2 paşi.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content