Fișierul intrare/ieșire | inversiuni.in, inversiuni.out | Sursă | Shumen Juniori 2013 |
---|---|---|---|
Autor | Stoyan Kapralov | Adăugată de | Radu Muntean • heracle |
Timp de execuție pe test | 0.8 sec | Limită de memorie | 9000 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Inversiuni
O permutare de ordin n este o secventa de n numere : a1, a2, a3, ..., an, in care fiecare numar de la 1 la n apare o singura data;
Doua numere dintr-o permutare, ai si aj, formeaza o inversiune daca ai > aj si i < j ;
De exemplu, in permutarea 4 2 7 1 5 6 3, exista in total 10 inversiuni intre numerele de pe pozitiile : 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3;
Cerinta
Scrieti un program care sa afiseze numarul total de inversiuni la o permutare data;
Date de intrare (in fisierul “inversiuni.in” )
Pe prima linie se va afla valoarea lui n, iar pe a doua linie cele n numere (delimitate prin spatiu) care formeaza permutarea.
Date de ieșire (in fisierul “inversiuni.out” )
Se va afisa un singur numar care prezinta numarul total de inversiuni a permutarii date.
Restricții
2 ≤ n ≤ 1000000
Exemplu
inversiuni.in | inversiuni.out |
---|---|
7 4 2 7 1 5 6 3 |
10 |