Задача Cool2k17. Назовем число «крутым», если в его десятичной записи присутствуют только цифры 0, 1, 2. Перестановка чисел A1, A2, ..., An лексикографически меньше перестановки B1, B2, ..., Bn, если существует k такое, что для всех i <k справедливо Ai = Bi и для Ak <Bk. Вам дано число N - длина перестановки (количество цифр в перестановке), а также число K - номер перестановки среди всех перестановок, отсортированных лексикографически. Вам необходимо найти количество «крутых» чисел, стоящих на «крутых» местах, то есть их индексы в перестановке также являются «крутыми» числами. Элементы в перестановке нумерованы с 1.
Технические условия. Программа Cool2k17 считывает с клавиатуры два числа N и K, оба не большем по 1018. Программа должна вывести единственное число - ответ задачи. В случае, если K-й перестановки не существует, следует вывести -1.
Примеры:
|
Ввод |
Вывод |
|
3 12 |
-1 |
|
3 4 |
1 |
Комментарий: Всего существует 6 перестановок чисел от 1 до 3. Это (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) (3, 2, 1). Поэтому на первый пример ответ 1 (двенадцатой перестановки не существует). На второй пример ответ 1 – в перестановке (2, 3, 1) только «крутое» число 2 стоит на «крутом» месте 1.