Ограничения: время – 250ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Выполним сортировку всех натуральных чисел от 1 до `N` следующим образом.
Переведем каждое число в двоичное представление (без ведущих нулей),
разряды числа запишем в обратном порядке в строку и выполним сортировку этих строк обычным образом, т.е. в лексикографическом порядке.
Лексикографический порядок — это способ упорядочивания слов в словаре, основанный на последовательном сравнении их букв.
Сравнение начинается с первой буквы, и если они совпадают, переходят ко второму и так далее, до тех пор, пока не будет найдено первое различие.
Слово будет считаться меньше другого слова, если оно закончилось раньше, чем было найдено различие (01 < 011), или
первая различающаяся буква расположена в алфавите раньше, чем соответствующая буква второго слова (10010 < 1010).
Например, для чисел от 1 до 8 получаем следующие строки:
Число | Двоичное представление | Строка
---|---:|---
1 | 1 | 1
2 | 10 | 01
3 | 11 | 11
4 | 100 | 001
5 | 101 | 101
6 | 110 | 011
7 | 111 | 111
8 | 1000 | 0001
После сортировки строк 1, 01, 11, 001, 101, 011, 111, 0001 получается последовательность
0001, 001, 01, 011, 1, 101, 11, 111.
Напишите программу, которая находит для нескольких чисел в диапазоне от 1 до `N`, где будет находиться строка, соответствующая этому числу
в упорядоченной последовательности.
Первая строка ввода содержит одно целое число `N` (`1<=N<=10^9`).
Вторая строка ввода содержит одно целое число `Q` (`1<=Q<=min(N,10^5)`) - количество чисел, для которых нужно найти номер строки в упорядоченной последовательности.
Далее следует `Q` строк, содержащих одно целое число `X_i` (`1<=X_i<=N`).
Вывести `Q` строк. В `i`-й строке вывести номер строки в упорядоченной последовательности, соответствующей `X_i`.
```sample Пример ввода:
8
3
1
7
4
```
```sample Вывод для примера:
5
8
2
```
*Система оценки и описание подзадач*
||.u|Подзадача 1 (50 баллов)||
`1<=N<=1000`, `1<=Q<=N`
||.u|Подзадача 2 (30 баллов)||
`1000<N<=10^5`, `1<=Q<=N`
Необходимые подзадачи: 1
||.u|Подзадача 3 (20 баллов)||
`10^5<N<=10^9`, `1<=Q<=10^5`
Необходимые подзадачи: 1, 2
Баллы за каждую из подзадач начисляются только в случае,
если все тесты для этой подзадачи успешно пройдены. По запросу сообщается результат о первой ошибке.
Начало
Рабочее место участника
Комбинаторика, теория Пойа