Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
190. Ouroboros Snake
Эйлеров путь/циклОлимпиадные задачи на русском языке
| 19/05/2007 | Практическое занятие 19 (E) |
| 09/03/2011 | Занятие 16 (B) |
| 26/03/2014 | Занятие 18 (B) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Уроборос — архаический образ, часто встречающийся в алхимических трактатах и представляющий собой змею, заглатывающую свой хвост.
Числа Уробороса – это двоичные числа из `2^n` бит, которые образованы из двоичных чисел 0 до `2^n-1` следующим образом. Для этого нужно разместить `2^n` бит по кругу, так чтобы получилось `2^n` различных подстрок из `n` бит при движении кругу.
Например, для `n=2` существует четыре числа Уробороса – 0011, 0110, 1100 и 1001. В таблице и на рисунке показано, как можно найти все подстроки в числе 0011:
| k | 00110011… | o(n=2,k) |
| 0 | 00 | 0 |
| 1 | 01 | 1 |
| 2 | 11 | 3 |
| 3 | 10 | 2 |
Ваше программа должна вычислять `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
