Fişierul intrare/ieşire:perm2.in, perm2.outSursăpreOJI 2004
AutorCristian George StratAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Permutari II

Se considera multimea A formata din elementele 1, 2, 3N (1N20.000).

O permutare P este o functie bijectiva definita pe multimea A, cu valori in A. (adica asociaza in mod unic fiecarui element din A un element unic tot din A).

Un exemplu de astfel de permutare este ilustrat de tabelul de mai jos

i1234
P(i)2341

Definim permutarea Pk astfel:

Pk(i) =

  • P(i), atunci cand k=1
  • P(Pk-1(i)), pentru k > 1

Tabelul de mai jos ilustreaza P1 si P2:

i1234
P1(i)2341
P2(i)3412

Cerinta

Se da N si o permutare P. Sa se gaseasca cel mai mic numar natural K strict pozitiv, astfel incat oricare ar fi 1iN avem Pk(i) = i (in alte cuvinte, Pk sa fie permutarea identica ).

Date de intrare

Fisierul perm2.in va contine pe prima linie numarul intreg N.

Pe urmatoarea linie se scriu N numere naturale distincte, fiecare in intervalul 1N.

Date de iesire

Pe prima linie a fisierului perm2.out se va scrie acel numar K ce indeplineste condiitle impuse.

Restrictii si precizari

  • Pentru testele furnizate 1K100.000

Exemple

perm2.inperm2.out
6
1 2 3 4 5 6
1
4
2 3 4 1
4
8
1 5 2 3 4 8 6 7
12
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content