Permutaciones feas P80445


Statement
 

pdf   zip

thehtml

En este problema, decimos que una permutación es k-fea si tiene exactamente k pares de posiciones adyacentes con dos números consecutivos. Dada una n, una k y m posiciones para las cuales ya se ha fijado el contenido, escribid todas las permutaciones k-feas de {0, …, n − 1} con el contenido fijado.

Entrada

La entrada consiste en diversos casos, cada uno con una n entre 1 y 10, seguida de una k entre 0 y n − 1, seguida de una m entre 0 y n, seguida de m pares i x, indicando que en la posición i tiene que haber una x. Suponed 0 ≤ y < n, 0 ≤ x < n, que todas las i son diferentes, y que todas las x son diferentes.

Salida

Para cada caso, escribid todas las permutaciones k-feas de {0, …, n − 1} con las posiciones fijadas, en orden lexicográfico. Escribid una línia con 20 asteriscos al final de cada caso.

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
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++