Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-12 00:19:34.
Revizia anterioară   Revizia următoare  

 

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

Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata.
Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii.

Se considera multimea A formata din elementele 1, 2, 3 ... N (1<=N<=20.000).

O permutare P este un functie bijectiva definita pe multimea A, cu valori in A. (bijectiva in sensul ca asociaza in mod unic fiecarui element din A un element 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 1<=i<=N 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 1..N.

Date de iesire

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

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

Restrictii si precizari

Pentru testele furnizate, 1<=K<=100.000

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?