H. Кейген 3
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Trey Frey - Refresh
⠀

Перестановка$$$^{\text{∗}}$$$ длины $$$n$$$ называется допустимой, если она обладает сразу двумя свойствами:

  • Она битоническая$$$^{\dagger}$$$;
  • Ровно $$$m$$$ её подмножеств являются циклами$$$^{\ddagger}$$$.

Обозначим $$$k$$$ как количество перестановок, удовлетворяющих вышеуказанному условию. Ваша задача — найти и напечатать $$$\min(k, 2000)$$$ примеров таких перестановок.

$$$^{\dagger}$$$ Перестановка $$$p_1, p_2, \ldots, p_n$$$ является битонической, если существует индекс $$$i$$$ ($$$1 \leq i \leq n$$$) такой, что

  • $$$p_{j-1} \leq p_j$$$ для $$$2 \leq j \leq i$$$;
  • $$$p_j \geq p_{j+1}$$$ для $$$i \leq j \leq n-1$$$.

$$$^{\ddagger}$$$ Подмножество $$$C \subseteq \{ 1, 2, \ldots, n \}$$$ является циклом, если оно удовлетворяет следующим условиям:

  • $$$C$$$ не пустое;
  • если $$$x \in C$$$, то $$$p_x \in C$$$;
  • $$$C$$$ минимально, т.е. не существует цикла $$$C'$$$, такого что $$$C' \subset C$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Входные данные состоит из одной строки, содержащей два целых числа $$$n$$$, $$$m$$$ ($$$1 \le m \leq n \le 100$$$) — длина перестановок и целевое количество циклов.

Выходные данные

В первой строке выведите одно целое число $$$r$$$: количество перестановок, которые вы собираетесь напечатать. Обратите внимание, что $$$r$$$ должно быть $$$\min(k, 2000)$$$, как указано в условии.

Затем выведите $$$r$$$ строк. Каждая строка должна содержать битоническую перестановку длины $$$n$$$, с $$$m$$$ циклами.

Пример
Входные данные
6 3
Выходные данные
9
1 4 5 6 3 2
6 5 4 3 2 1
1 2 4 5 6 3
1 2 5 6 4 3
1 3 4 6 5 2
1 5 6 4 3 2
3 5 6 4 2 1
1 3 6 5 4 2
2 6 5 4 3 1
Примечание

В примере существует $$$9$$$ допустимых перестановок (т.е. битонических перестановок длины $$$6$$$, с $$$3$$$ циклами). Например, $$$[3, 5, 6, 4, 2, 1]$$$ является битонической (в приведенном выше определении, $$$i = 3$$$), и она имеет $$$3$$$ цикла: $$$\{1, 3, 6\}$$$, $$$\{2, 5\}$$$, $$$\{4\}$$$. Таким образом, вы должны напечатать $$$r = \min(9, 2000) = 9$$$ таких перестановок.