e-olymp 1519. Коды Грея

Задача

Френк Грей. Bell Lab 1930

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

Входные данные

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

Выходные данные

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

Входные данные Выходные данные
1 14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
0
1
0
1
3
2
0
1
3
2
6
7
5
4
2 3
2 1
1 2
3 3
1
1
2
3 1
0 0
0
4 2
2 3
1 3
2
1

Код программы

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

e-olymp 8643. Иннолошадь

Задача

В шахматном иннокоролевстве выводят специальные породы инноконей. Порода инноконя задается парой чисел $(x, y), 0 ≤ x ≤ y$. Инноконь перемещается следующим образом: сначала перемещается на $x$ клеток в одну из четырех сторон, затем поворачивает на 90 градусов влево или вправо и перемещается еще на $y$ клеток. Например, обычный шахматный конь — это инноконь породы (1, 2).

Петя и Вася недавно видели инноконя, он прыгнул с поля $A$ на поле $B$. Пете и Васе стало интересно, какой породы был этот инноконь. Помогите им ответить на этот вопрос.

Входные данные

Шахматная доска состоит из 8 строк и 8 столбцов. Строки нумеруются числами от 1 до 8, а столбцы буквами от $a$ до $h$. Таким образом, каждое поле задается парой из буквы и цифры. В двух строках ввода содержатся описания полей $A$ и $B$.

Выходные данные

Выведите два целых числа $x$ и $y$, $(0 ≤ x ≤ y)$, соответствующие породе данного инноконя.

Тесты

Входные данные Выходные данные
a1 b3 1 2
g5 d3 2 3
e1 e1 0 0
d3 d7 0 4
a2 c2 0 2

Код программы

Решение

Найдем разницы пройденных расстояний по строкам и столбцам. Тогда породой данного инноконя будет пара этих чисел, размещенных по возрастанию.

e-olymp

ideone

e-olymp 4717. Дележ яблок — 2

Задача

$n$ школьников делят $k$ яблок поровну, не делящийся остаток остаётся в корзинке. Сколько яблок останется в корзинке?

Входные данные

Два положительных целых числа $n$ и $k$, не больших 1500.

Выходные данные

Вывести количество яблок, которое останется в корзинке.

Тесты

Входные данные Выходные данные
200 300 100
1500 1500 0
30 600 0
12 15 3
152 1432 64

Код программы

Решение

Ответом является остаток от деления $k$ на $n$.

e-olymp

ideone