printРабочее место участника

printЗадачи

190. Ouroboros Snake

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Уроборос — архаический образ, часто встречающийся в алхимических трактатах и представляющий собой змею, заглатывающую свой хвост.
Числа Уробороса – это двоичные числа из `2^n` бит, которые образованы из двоичных чисел 0 до `2^n-1` следующим образом. Для этого нужно разместить `2^n` бит по кругу, так чтобы получилось `2^n` различных подстрок из `n` бит при движении кругу.
Например, для `n=2` существует четыре числа Уробороса  – 0011, 0110, 1100 и 1001. В таблице и на рисунке показано, как можно найти все подстроки в числе 0011:

k00110011…o(n=2,k)
0000
1 011
2  113
3   102
Ваше программа должна вычислять `o(n,k)`, где `n\ >\ 0` и `0\ ≤\ k\ <\ 2^n`. Эта функция вычисляет `k`-е число в наименьшем числе Уробороса порядка `n`.
В первой строке ввода содержится одно целое число `T\ (0\ <\ T\ <\ 300)` – число тестов. Далее следует `T` строк, в каждой строке содержится два целых числа `n\ (0<n<22)` и `k\ (0\ ≤\ k\ <\ 2^n`).
Для каждого теста вы должны вычислить функцию `o(n,k)` и напечатать результат на отдельной строке.

Пример ввода

4 
2 0
2 1
2 2
2 3

Вывод для примера

0
1
3
2
Source: ACM ICPC Mid-Central European RC, 2000
loading