Permutacions lletges P80445

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.