D'un a ena (3) P69756


Statement
 

pdf   zip

html

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++