Размещения без крутых спусков

시간 제한1초메모리 제한1024 MB

요약

1부터 n까지의 수 중 서로 다른 k개를 골라 만든 순열 가운데, 이웃한 수가 1을 초과해 줄어드는 구간이 없는 모든 순열을 사전순으로 출력한다.

난이도: 보통10점 중 4점
유형: 백트래킹, 재귀, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Размещением из $n$ по $k$ называется массив $a\[1..k]$ , содержащий $k$ различных натуральных чисел, каждое из которых находится в диапазоне от $1$ до $n$ .

Пара подряд идущих элементов размещения $a\[i], a\[i + 1]$ называется спуском, если $a\[i] > a\[i+1]$ . Спуск называется крутым, если $a\[i] > a\[i + 1] + 1$ .

По заданным $n$ и $k$ требуется вывести все размещения из $n$ по $k$ без крутых спусков. Размещения необходимо упорядочить по первому числу, при равенстве первого --- по второму, затем по третьему и так далее.

입력

Первая строка ввода содержит натуральное число $n$ , вторая строка ввода содержит натуральное число $k$ ( $1 \le k \le n \le 13$ ).

출력

Выведите все размещения из $n$ по $k$ без крутых списков, по одному на строке. Внутри размещения разделяйте числа пробелами.

예제1

예제 1
입력
```
3
2
```
예상 출력
```
1 2
1 3
2 1
2 3
3 2
```