Fişierul intrare/ieşire: | perm3.in, perm3.out | Sursă | info-arena 1.0 |
Autor | Eugen Neamtiu | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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:
- { 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.
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
Date de Intrare
Fisierul de intrare perm3.in contine:
Valori | Semnificatie |
---|---|
N | prima linie: N = numarul de elemente al multimii, |
m1 m2 m3 ... mN | a doua linie: elementele multimii, in ordine crescatoare |
p1 p2 p3 ... pN | a treia linie: elementele permutarii (elementele m1 m2 m3 ... mN dar in alta ordine) |
Date de Iesire
Fisierul de iesire perm3.out va contine numarul permutarii in ordine lexicografica.
Restrictii si precizari
- 1 ≤ N ≤ 1.000
- 1 ≤ mi ≤ 2.000.000.000
Exemplu
perm3.in | perm3.out |
---|---|
3 1 23 25 23 1 25 | 3 |
4 1 2 3 4 3 4 1 2 | 17 |