Məsələlər
Битовая сортировка
Битовая сортировка
На множестве неотрицательных целых чисел введем следующее отношение порядка: будем считать, что число A меньше числа B в двух случаях:
- Когда в двоичной записи у числа A меньше единиц, чем у B.
- Когда в двоичной записи у числа A столько же единиц как и у B, и A меньше B в обычном смысле.
Теперь отсортируем по возрастанию множество всех целых чисел от 0 до n включительно, используя это новое отношение порядка. Ваша задача - найти какое число будет находиться на позиции k. Нумерация позиций ведется с единицы.
Входные данные
Первая строка содержит целые числа n и k (0 ≤ n ≤ 1016
, 1 ≤ k ≤ n + 1).
Выходные данные
Вывести k-ое число в отсортированной последовательности.
Пояснение
Числа от 0 до 10 будут отсортированы следующим образом: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 7.
Giriş verilənləri #1
10 7
Çıxış verilənləri #1
5