== include(page="template/taskheader" task_id="perm5") ==
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
Numim grad al unei permutari cel mai mic numar natural $k > 0$, astfel incat
* $p^k^ = 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$).
h2. 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.
h2. Date de intrare
Fisierul de intrare $perm5.in$ contine pe prima linie numarul natural nenul $N$.
...
h2. 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.
...
h2. Restrictii
* $1 ≤ N ≤ 2000$
* Prin operatia $o$ intelegem compunerea functiilor. Mai exact $pop(i) = p(p(i))$, pentru orice $i = 1, 2, ..., N$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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.
...
== include(page="template/taskfooter" task_id="perm5") ==
