Diferente pentru problema/perm6 intre reviziile #8 si #22

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="perm6") ==
Se dau doua numere naturale $N$ si $K$. Sa se tipareasca numarul de permutari ale multimii {$1, 2, ..., N$} in care exista $K$ inversiuni. Dandu-se o permutare $P$, numarul de inversiuni al ei este numarul de perechi (i,j) pentru care @i<j si P[i]>P[j]@. De exemplu, pentru permutarea cu 5 elemente: $P=52314$, perechile (i,j) in dezordine sunt:
$(1,2):    1<2 dar 5>2 $
Se dau doua numere naturale $N$ si $K$. Sa se tipareasca numarul de permutari ale multimii {$1, 2, ..., N$} in care exista $K$ inversiuni. Dandu-se o permutare $P$, numarul de inversiuni al ei este numarul de perechi $(i,j)$ pentru care @i<j si P[i]>P[j]@. De exemplu, pentru permutarea cu $5$ elemente: $P=5 2 3 1 4$, perechile $(i,j)$ in dezordine sunt:
$(1,2)$:    1<2 dar 5>2
$(1,3)$:    1<3 dar 5>3
$(1,4)$:    1<4 dar 5>1
$(1,5)$:    1<5 dar 5>4
$(2,4)$:    2<4 dar 2>1
$(3,4)$:    3<4 dar 3>1
Asadar permutarea in cauza are 6 inversiuni. Numarul minim de inversiuni al unei permutari de $N$ elemente este 0 (pentru permutarea $1 2 3 ... N-1 N$), iar numarul maxim de inversiuni este $N*(N$-1)/2 (pentru permutarea $N N-1 ... 3 2 1$).
Asadar permutarea in cauza are 6 inversiuni. Numarul minim de inversiuni al unei permutari de $N$ elemente este 0 (pentru permutarea $1 2 3 ... N-1 N$), iar numarul maxim de inversiuni este $N*(N-1)/2$ (pentru permutarea $N N-1 ... 3 2 1$).
h2. Date de intrare
h2. Date de iesire
Fisierul $perm6.out$ va contine numarul de permutari cu K inversiuni.
Fisierul $perm6.out$ va contine numarul de permutari cu $K$ inversiuni.
h2. Restrictii
== include(page="template/taskfooter" task_id="perm6") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2196