201272: [AtCoder]ARC127 C - Binary Strings
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $500$ points
Problem Statement
Snuke has written on a blackboard every integer from $1$ through $(2^N-1)$, in binary.
Find the $X$-th lexicographically smallest string when seeing the integers on the blackboard as strings.
Here, the input gives $N$ in decimal, but $X$ in binary.
Constraints
- $1 \leq N \leq 10^6$
- $1 \leq X \leq 2^N-1$
- $X$ is in binary.
Input
Input is given from Standard Input in the following format:
$N$ $X$
Output
Print the answer.
Sample Input 1
3 101
Sample Output 1
11
The strings written on the blackboard in lexicographical order are 1
, 10
, 100
, 101
, 11
, 110
, 111
.
Additionally, we have $X=101(\mathrm{binary})=5(\mathrm{decimal})$.
Thus, the answer is 11
.
Sample Input 2
10 10100011
Sample Output 2
1001001111
Sample Input 3
1000000 11111
Sample Output 3
1000000000000000000000000000000