Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-12 00:14:46.
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.in

6

1 2 3 4 5 6

perm2.out

1

perm2.in

4

2 3 4 1

perm2.out

4

perm2.in

8

1 5 2 3 4 8 6 7

perm2.out

12

Precizari

Pentru testele furnizate, 1<=K<=100 000

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?