perm2

Permutari II

== include(page="template/taskheader" task_id="perm2") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| perm2.in | perm2.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="perm2") ==

==Include(page="template/taskheader" task_id="perm2")==
==Include(page="template/raw")==
 
Permutari
 
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 P^k astfel:
 
P^k(i)= P(i), daca k=1
 
Sau
 
P(P^k-1(i)), pentru k>1
 
Tabelul de mai jos ilustreaza P^1 si P^2:
 
 
|I |1 |2 |3 |4 |
 
|P^1(i) |2 |3 |4 |1 |
 
|P^2(i) |3 |4 |1 |2 |
 
h2. 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 P^k(i)=i (in alte cuvinte, P^k sa fie "permutarea identica").
 
h2. 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.
 
h2. 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
==Include(page="template/taskfooter" task_id="perm2")==