Fişierul intrare/ieşire:perm5.in, perm5.outSursăLot Suceava 2007
AutorEmanuela CerchezAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inperm5.out
52 1 4 5 3
142 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content