Nu exista diferente intre titluri.
Diferente intre continut:
==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
==Include(page="template/taskheader" task_id="perm2")==
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
table(numbers). |_. $i$ | $1$ |$2$ |$3$ |$4$ |
|_. $P(i)$ |$2$ |$3$ |$4$ |$1$ |
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$ avem $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. Restrictii si precizari
* Pentru testele furnizate $1$ ≤ $K$ ≤ $100.000$
h2. Exemple
table(example). |_. 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 |
==Include(page="template/taskfooter" task_id="perm2")==
12
Precizari
Pentru testele furnizate, 1<=K<=100 000
==Include(page="template/taskfooter" task_id="perm2")==
Nu exista diferente intre securitate.
Diferente intre topic forum: