== include(page="template/taskheader" task_id="perm6") ==
Poveste si cerinta...
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
(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).
h2. Date de intrare
...
Fisierul $perm6.in$ contine o singura linie pe care se afla valorile lui $N$ si $K$, despartite printr-un spatiu.
h2. Date de iesire
...
Fisierul $perm6.out$ va contine numarul de permutari cu K inversiuni.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 45$
* $0 ≤ K ≤ N*(N-1)/2$
h2. Exemplu
table(example). |_. perm6.in |_. perm6.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 0
| 1
|
h3. Explicatie
...
table(example). |_. perm6.in |_. perm6.out |
| 4 2
| 5
|
== include(page="template/taskfooter" task_id="perm6") ==
