Permutacions lletges P80445


Statement
 

pdf   zip

thehtml

En aquest problema, diem que una permutació és k-lletja si té exactament k parells de posicions adjacents amb dos nombres consecutius. Donada una n, una k i m posicions per a les quals ja s’ha fixat el contingut, escriviu totes les permutacions k-lletges de {0, …, n − 1} amb el contingut fixat.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 10, seguida d’una k entre 0 i n − 1, seguida d’una m entre 0 i n, seguida de m parells i x, indicant que a la posició i hi ha d’haver una x. Suposeu 0 ≤ i < n, 0 ≤ x < n, que totes les i són diferents, i que totes les x són diferents.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les permutacions k-lletges de {0, …, n − 1} amb les posicions fixades. Escriviu una línia amb 20 asteriscs al final de cada cas.

Public test cases
  • Input

    2 1 0
    
    1 0 0
    
    3 2 1
    1 2
    
    5 2 2
    4 0
    3 2
    
    5 0 2
    4 0
    3 2
    

    Output

    0 1
    1 0
    ********************
    0
    ********************
    ********************
    1 4 3 2 0
    3 4 1 2 0
    4 3 1 2 0
    ********************
    3 1 4 2 0
    ********************
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++