infoarena

Cum rezolvati problema asta ?
Problema 2 - Permutari 100 puncte
Se considera multimea A formata din elementele 1, 2, 3, … ,N (1 ≤ N ≤ 1200).
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 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 P1 si P2:
i 1 2 3 4
P¹( i ) 2 3 4 1
P²( 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 P^k(i) = i (cu alte cuvinte, P^k sa fie permutarea identica ).
Date de intrare
Fisierul perm.in va contine pe prima linie numarul intreg N.
Pe urmatoarea linie se scriu N numere naturale distincte, fiecare din intervalul 1 … N, reprezentând permutatea iniţială P.
Date de iesire
Pe prima linie a fisierului perm.out se va scrie acel numar K ce indeplineşte condiţiile impuse.
Restrictii si precizari
• Timp de executie/test:1 secunda
Exemple
perm.in Perm.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

Eu am incercat ceva de genu : incep de la i=n, daca p[ i ]<p[ i-1 ] atunci interschimb, nr++ si i=n+1; si tot asa 
Si afisez nr. Dar pt exemplu 2 nu merge, si asta era un test . voi cum ati rezolva-o?
Si nu apare o neconcordanta  ei mai sus in text dau:
1 2 3 4
si P¹ 2 3 4 1
Si in exemple dau:    ca ii de ordin 4 (P⁴).

Problema se gaseste aici (http://infoarena.ro/problema/perm2). Poti incerca sa cauti hinturi pe topicul corespunzator problemei. Nu se publica solutii complete la problemele din arhiva.

Multumesc pentru  link. N-am cerut rezolvarea completa, nici nu o vreau... doar  dorema niste hinturi.
Dar  , nu apare o neconcordanta  ei mai sus in text dau:
1 2 3 4
si P¹ 2 3 4 1
Si in exemple dau:    ca ii de ordin 4 (P⁴). Aici nu inteleg?

Pai e corect:

P¹ : 2 3 4 1
P² : 3 4 1 2
P³ : 4 1 2 3
P⁴ : 1 2 3 4

Deci permutarea are ordin 4.

multumesc. Am inteles-o si eu ....intr-un final   \:D/ ,acum  doar trebuie  sa  optimizez solutia mea. Pacat ca n-am facut-o si la oli,   mi-ar fi fost de folos :)

ai primit problema asta la oli??
adik e fix enuntul pe care l-ai postat mai sus?

Da, daca vrei poti downlada de aici http://tminfo.info/index.php?Pages=Concursuri&foodar=18  si mergi la OLI2009.zip.
Este vreo  problema?

E copy/paste la perm2 :))

Si atunci.....ar trebuii sa reformulez  problema postata de mine, pe acest topic ? sau iei,adica cei din comisie, platesc  drepturi de  autor? :)
Au afisat codul de la rezolvarea propusa de ei, am incercat-o pe sit, nu ia mai mult de  85pct    :rotfl:
Exista numarul lui Stirling de speta 1?

Am observat ca la mai multe concursuri in ultimul timp se dau probleme de pe infoarena :roll:

Concluzia imediata pe care o trag este ca ar trebui sa lucrati cat mai mult din arhiva noastra :winner1:

da, pai  sincer va zic aveti probleme destul de faine, care chiar te pun sa te gandesti, sa judeci . Sper ca la oji sa am mai mult succes :)