==Include(page="template/taskheader" task_id="perm3")==
==Include(page="template/raw")==
Link: [1]File-List
permutari 3
Pentru o multime oarecare de numere intregi cu N elemente se poate defini o permutare a acesteia ca fiind o varianta de a aseza elementele multimii. De exemplu pentru multimea M={4,12,81} vom avea permutarile:
1) { 4 , 12 , 81 }
2) { 4 , 81 , 12 }
3) { 12 , 4 , 81 }
4) { 12 , 81 , 4 }
5) { 81 , 4 , 12 }
6) { 81 , 12 , 4 }
In grupul format de toate permutarile unei multimi se poate defini o ordine a acestora astfel incat elementele aflate pe prima pozitie sa fie in ordine crescatoare, elementele de pe a doua pozitie sa fie in ordine crescatoare pentru permutarile care au primul element identic, etc. asa cum se vede in figura. O astfel de ordine se numeste ordine lexicografica. Permutarilor asezate in ordine lexicografica li se pot asocia numere de ordine, in cazul exemplului de mai sus de la 1) la 6).
h2. Cerinta
Dandu-se o multime de numere intregi si o permutare a ei concepeti un program care determina numarul de ordine al permutarii in ordine lexicografica
h2. Date de Intrare
Fisierul de intrare perm3.in contine:
|Valori |]Semnificatie |
|N |prima linie: N = numarul de elemente al multimii, 1 <= N <= 1.000 |
|m[1] m[2] m[3] ... m[N|a doua linie: elementele multimii, in ordine crescatoare, 1 <= m[i] <= 2.000.000.000 |
|]p[1] p[2] p[3] ...|a treia linie: elementele permutarii (elementele m[1] m[2] m[3] ... m[N] dar in alta ordine) |
h2. Date de Iesire
Fisierul de iesire perm3.out va contine numarul permutarii in ordine lexicografica.
h2. Exemplu
|perm3.in |perm3.out |
|3 |3 |
| | |
|1 23 25 | |
| | |
|23 1 25 | |
|4 |17 |
| | |
|1 2 3 4 | |
| | |
|3 4 1 2 | |
==Include(page="template/taskheader" task_id="perm3")==
Pentru o multime oarecare de numere intregi cu $N$ elemente se poate defini o permutare a acesteia ca fiind o varianta de a aseza elementele multimii. De exemplu pentru multimea $M={4,12,81}$ vom avea permutarile:
# ${ 4 , 12 , 81 }$
# ${ 4 , 81 , 12 }$
# ${ 12 , 4 , 81 }$
# ${ 12 , 81 , 4 }$
# ${ 81 , 4 , 12 }$
# ${ 81 , 12 , 4 }$
In grupul format de toate permutarile unei multimi se poate defini o ordine a acestora astfel incat elementele aflate pe prima pozitie sa fie in ordine crescatoare, elementele de pe a doua pozitie sa fie in ordine crescatoare pentru permutarile care au primul element identic, etc. asa cum se vede in figura. O astfel de ordine se numeste ordine lexicografica. Permutarilor asezate in ordine lexicografica li se pot asocia numere de ordine, in cazul exemplului de mai sus de la $1$ la {$6$}.
h2. Cerinta
Dandu-se o multime de numere intregi si o permutare a ei concepeti un program care determina numarul de ordine al permutarii in ordine lexicografica
h2. Date de Intrare
Fisierul de intrare $perm3.in$ contine:
|_. Valori |_. Semnificatie |
|{$N$} |prima linie: $N$ = numarul de elemente al multimii, |
|{$m{~1~} m{~2~} m{~3~}$} ... {$m{~N~}$}|a doua linie: elementele multimii, in ordine crescatoare|
|{$p{~1~} p{~2~} p{~3~}$} ... {$p{~N~}$}|a treia linie: elementele permutarii (elementele {$m{~1~} m{~2~} m{~3~}$} ... {$m{~N~}$} dar in alta ordine) |
h2. Date de Iesire
Fisierul de iesire $perm3.out$ va contine numarul permutarii in ordine lexicografica.
h2. Restrictii si precizari
* $1 ≤ N ≤ 1.000$
* $1 ≤ m{~i~} ≤ 2.000.000.000$
h2. Exemplu
table(example). |_. perm3.in |_. perm3.out |
| 3
1 23 25
23 1 25
| 3 |
| 4
1 2 3 4
3 4 1 2
| 17 |
==Include(page="template/taskfooter" task_id="perm3")==
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/perm3/permutari.files/filelist.xml
==Include(page="template/taskfooter" task_id="perm3")==
