| Fişierul intrare/ieşire: | sortari2.in, sortari2.out | Sursă | RMMS 2011 - Ziua 2 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.in | sortari2.out |
|---|---|
| 4 | 11 |
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.
