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