Fişierul intrare/ieşire:perm6.in, perm6.outSursăLista lui Francu
AutorCatalin FrancuAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.10 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perm 6

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).

Date de intrare

Fisierul perm6.in contine o singura linie pe care se afla valorile lui N si K, despartite printr-un spatiu.

Date de iesire

Fisierul perm6.out va contine numarul de permutari cu K inversiuni.

Restrictii

  • 1 ≤ N ≤ 45
  • 0 ≤ K ≤ N*(N-1)/2

Exemplu

perm6.inperm6.out
3 0
1
perm6.inperm6.out
4 2
5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content