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
 Continutul acestei pagini nu este formatat conform recomandarilor de formatare.Daca aveti permisiunile necesare, va rugam sa il imbunatatiti. |
Se considera multimea A formata din elementele 1, 2, 3 … N (1 ≤ N ≤ 20.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
| 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 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 1 … N.
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 1 ≤ K ≤ 100.000
Exemple
| perm2.in | perm2.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 |
