Будем восстанавливать нашу последовательность, начиная с самого левого элемента.
Пускай длина последовательности равна N, и мы предполагаем, что на самой левой позиции стоит число x. Это значит, что все числа от 1 до (x-1) уже стояли на этой позиции, и для каждой из них существовало
(N-1)! различных упорядочиваний "непервых" чисел. Следовательно, число x должно быть таким, что
(x-1)*(N-1)! K. При маленьких ограничениях на N, такое число подобрать не сложно.
Рассмотрим теперь, как восстановить число, стоящее на i-той слева позиции, зная какие числа стоят на позициях от 1 до i-1. Как в случае для i = 1, раньше x при установленных предыдущих позициях здесь могли стоять только числа меньше x, но на этот раз в это множество не могут входить числа, совпадающие с левее стоящими, поэтому, во-первых, x стоит не на x-той, а на x-b-той позиции, где b - кол-во чисел меньших x и уже занявших фиксированную позицию слева. Во-вторых, функция факториал применяется не к N-1, а к (N-i). В-третьих, после определения каждой цифры, надо уменьшать требуемый номер на количество отсечённых на предыдущем ходе номеров (x-b)*(N-i)!.
После выполнения описанных действий для всех позиций кроме правой, K станет равно 1 и неиспользован-
ным останется только 1 число.
Найдите перестановку по её номеру в лексикографическом порядке.
Входные данные
В первой строке входных данных содержится число N (1 <= N <= 12) – количество элементов в перестановке, во второй – число K (1 <= K <= N!) – номер перестановки.