perm2

Permutari II

== include(page="template/taskheader" task_id="perm2") ==

==Include(page="template/taskheader" task_id="perm2")==

Poveste ...

==Include(page="template/raw")==
 
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

h2. Cerinta
...

table(numbers). |_. i |1 |2 |3 |4 |
|_. $P(i)$ |2 |3 |4 |1 |

h2. Restrictii

Definim permutarea $P^k^$ astfel:

...

$P^k^(i)$ =
 * $P(i)$, atunci cand $k=1$
 * $P(P^k^-1(i))$, pentru $k > 1$
 
Tabelul de mai jos ilustreaza P^1^ si P^2^:
 
table(numbers). |_. 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.
 
h2. 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

h2. Exemplu

12

| perm2.in | perm2.out |
| linia1
linia2
linia3
| linia1
linia2
|

Precizari

== include(page="template/taskfooter" task_id="perm2") ==
 

Pentru testele furnizate, 1<=K<=100 000
==Include(page="template/taskfooter" task_id="perm2")==