D'un a ena (3) P69756

Statement

thehtml

Feu un programa que escrigui totes les permutacions de { 1, …, n } amb k inversions, per a una n i una k donades. Una inversió és una parella d’elements x i y tals que x > y i tals que x apareix a la permutació abans que y.

Entrada

L’entrada consisteix en dos naturals n i k, tals que n ≥ 1 i 0 ≤ k ≤ n(n − 1)/2.

Sortida

Escriviu totes les permutacions de { 1, …, n } amb k inversions.

Informació sobre el corrector

Podeu escriure les solucions d’aquest exercici en qualsevol ordre.

Pista

Aquí, un algorisme molt simple pot ser massa lent.

Public test cases

Input

5 2

Output

(1,2,4,5,3)
(1,2,5,3,4)
(1,3,2,5,4)
(1,3,4,2,5)
(1,4,2,3,5)
(2,1,3,5,4)
(2,1,4,3,5)
(2,3,1,4,5)
(3,1,2,4,5)

Input

10 45

Output

(10,9,8,7,6,5,4,3,2,1)

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++ Python