Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | perm2.in, perm2.out | Sursă | preOJI 2004 |
| Autor | Cristian George Strat | Adăugată de | |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
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
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| P(i) | 2 | 3 | 4 | 1 |
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:
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| P1(i) | 2 | 3 | 4 | 1 |
| P2(i) | 3 | 4 | 1 | 2 |
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
