Informatica Online Judge

  우로보로스 수 [1018 / 03FA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 17   Total Tried : 21


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[LavidaOJ]

Background

우로보로스 수는 0부터 2n-1의 모든 숫자를 포함하는 이진수이며, 2n개의 비트로 이뤄진 숫자를 원의 형태로 둥글게 만들어 놓아 맨 마지막 숫자 뒤에 맨 앞의 숫자가 오게 한다. 이렇게 배치한 숫자들의 연속된 n비트를 읽게 되면 0부터 2n-1의 모든 숫자가 존재할 수 있다.

예를 들어 n=2이면 4비트로 구성되는 이진수들 중에서 우로보로스 수는 0011, 0110, 1100, 1001 등을 찾을 수 있다. 여기서, 우로보로스 수 0011의 경우 다음의 그림, 표를 통해 길이가 2인 모든 이진수를 찾을 수 있음을 알 수 있다.



n이 주어졌을 때 2n비트에 대한 가장 작은 우로보로스 수에 대해 맨 앞에서부터 읽었을 때 k번째부터 n자리의 이진수를 읽어 10진수로 변환하는 값을 출력하는 프로그램을 작성하시오.

Input

입력의 첫 줄에는 양의 정수 n, k가 입력된다.

[입력값의 정의역]
1 <= n <= 20
0 <= k <= 2n-1

[Sub-task Info]
#1 : n <= 5
#2 : n <= 10
#3 : n <= 15
#4 : n <= 20

Output

k번째부터 n자리의 이진수를 읽어 10진수로 변환하는 값을 출력한다.

IO Example

입력
2 3

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]