ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2007 > задача:

B. Bitsorting

Задачи сборника

• A. Phalanx
• B. Bitsorting
• C. Cubes
• D. Factorial
• E. Lights
• F. Parliament
• G. Strange Numbers
• H. Two Captains
• I. Boundary Troops
• J. Wedding

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ. Сложность Гамма

For the set of all non-negative integers let's introduce the following order relation: let's admit that number A is less than number B in two cases:

• When the binary notation of A has fewer "ones" than B has.
• When the binary notation of A contains the same amount of "ones" that B has, and A is less than B in usual meaning.

Now sort out the set of integers, from 0 to N inclusive, in ascending order using this new order relation. Your task is to find the number, placed in position K. The numeration of the positions begins from 1.

The first line of the input contains the integers N and K (0 ≤ N ≤ 1016; 1 ≤ KN+1).
The output should contain one number which is the answer to the question.

Input 1 Output 1
10 7

Comment on the example: the integers from 0 to 10 will be sorted in the following way: 0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 7.

Для отправки решений необходимо выполнить вход.