Problem2065--一个二进制问题

2065: 一个二进制问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 33  Solved: 6
[Status] [Submit] [Creator:]

Description

对于任何一个十进制正整数,我们都可以将其转成二进制的形式。比如:
· 十进制数 10 对应的二进制数为 1010;
· 十进制数 35 对应的二进制数为 100011;
· 十进制数 123 对应的二进制数为 1111011。
其中,10 的二进制表示中 1 的位数为 2;35 的二进制表示中 1 的位数为 3;123 的二进制表示中 1 的位数为 6。

请你找出所有二进制表示中 1 的位数为 p 的正整数中第 k 小的那个整数。

Input

输入共一行,包含两个整数 p 和 k,以一个空格分隔(1 ≤ p < 30, 1 ≤ k ≤ 107 且数据保证答案不超过 109)。

Output

输出一个整数,表示二进制表示中 1 的位数为 p 的正整数中第 k 小的那个整数(你需要输出的是这个数对应的十进制形式)。

Sample Input Copy

【样例输入1】
3 10
【样例输出1】
28
【样例输入2】
5 20
【样例输出2】
122

HINT

样例解释

样例1:
前 10 个二进制表示中 1 的位数为 3 的正整数如下:
· 7,对应的二进制数为 111
· 11,对应的二进制数为 1011
· 13,对应的二进制数为 1101
· 14,对应的二进制数为 1110
· 19,对应的二进制数为 10011
· 21,对应的二进制数为 10101
· 22,对应的二进制数为 10110
· 25,对应的二进制数为 11001
· 26,对应的二进制数为 11010
· 28,对应的二进制数为 11100
样例2:
前 20 个二进制表示中 1 的位数为 5 的正整数如下:
· 31,对应的二进制数为 11111
· 47,对应的二进制数为 101111
· 55,对应的二进制数为 110111
· 59,对应的二进制数为 111011
· 61,对应的二进制数为 111101
· 62,对应的二进制数为 111110
· 79,对应的二进制数为 1001111
· 87,对应的二进制数为 1010111
· 91,对应的二进制数为 1011011
· 93,对应的二进制数为 1011101
· 94,对应的二进制数为 1011110
· 103,对应的二进制数为 1100111
· 107,对应的二进制数为 1101011
· 109,对应的二进制数为 1101101
· 110,对应的二进制数为 1101110
· 115,对应的二进制数为 1110011
· 117,对应的二进制数为 1110101
· 118,对应的二进制数为 1110110
· 121,对应的二进制数为 1111001
· 122,对应的二进制数为 1111010

数据规模与约定

· 对于 30% 的数据,1 ≤ p ≤ 5, 1 ≤ k ≤ 10
· 对于 60% 的数据,1 ≤ p ≤ 10, 1 ≤ k ≤ 1000
· 对于 100% 的数据,1 ≤ p < 30, 1 ≤ k ≤ 107
数据保证答案肯定不超过 109

Source/Category