Fișierul intrare/ieșire inversiuni.in, inversiuni.out Sursă Shumen Juniori 2013
Autor Stoyan Kapralov Adăugată de avatar heracle Radu Muntean heracle
Timp de execuție pe test 0.8 sec Limită de memorie 9000 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii