Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | perm5.in, perm5.out | Sursă | Lot Suceava 2007 |
| Autor | Emanuela Cerchez | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Perm 5
Fie N un numar natural si p = (p1, p2, ..., pN) o permutare de ordin N.
Numim grad al unei permutari cel mai mic numar natural k > 0, astfel incat
- pk = popop...op (de k ori) = e
(unde cu e am notat permutare identica, deci permutarea pentru care e(i) = i, pentru orice i = 1, 2, ..., n).
Cerinta
Pentru un N dat, sa se determine o permutare de ordin N avand grad maxim. Daca exista mai multe solutii se va determina prima in ordine lexicografica.
Date de intrare
Fisierul de intrare perm5.in contine pe prima linie numarul natural nenul N.
Date de iesire
Fisierul de iesire perm5.out va contine o singura linie pe care vor fi scrise N numere naturale distincte cuprinse intre 1 si N, separate prin cate un spatiu, reprezentand prima permutare de grad maxim in ordine lexicografica.
Restrictii
- 1 ≤ N ≤ 2000
- Prin operatia o intelegem compunerea functiilor. Mai exact pop(i) = p(p(i)), pentru orice i = 1, 2, ..., N.
Exemplu
| perm5.in | perm5.out |
|---|---|
| 5 | 2 1 4 5 3 |
| 14 | 2 3 1 5 6 7 4 9 10 11 12 13 14 8 |
Explicatie
Permutarea (2, 1, 4, 5, 3) are gradul 6 (maxim posibil).
Exista si alte solutii, dar aceasta este cea mai mica din punct de vedere lexicografic.
