Двоичные строки заданной длины

2

00
01
10
11

Тихий Дон №1

Мир XOR

Пусть \(F(A, B) = A \oplus (A+1) \oplus (A+2) \oplus ... \oplus B\), где \(\oplus\) - операция исключающее ИЛИ (XOR).
По известным числам A и B посчитайте F(A, B).

Входные данные
На вход подается строка, содержащая 2 числа: A и B (0 <= A, B <= 10¹²).

Выходные данные
Выведите F(A, B). 
 

Примеры

XOR мешанина

 У Громозеки есть n-1 целое число, записанные на карточках и разложенные в ряд в произвольном порядке. Он вычислил побитовый исключающий ИЛИ (xor) между всеми записанными числами. Вычисленное число (X) он записал на новую карточку и добавил ее в конец всех карточек с числами. Теперь у него есть n карточек с числами. Он перемешал все карточки и снова разложил их в ряд в произвольном порядке. 

Громозека показал вам все n карточек и просит вас угадать число X, которое было записано на новой карточке.

Входные данные
Первая строка входных данных содержит целое число n - количество карточек с числами (2 <= n <= 100). Вторая строка содержит n целых чисел - числа записанные на карточках (каждое число принадлежит промежутку [0, 127]). 

Выходные данные
Выведите ответ одно целое число - число X, которое было записано на новой карточке.
Гарантируется, что ответ существует. Если ответов несколько, выведите минимальное значение X.
 
 

Примеры

Максимальный XOR - 2

Два числа a и b записаны в шестнадцатеричной системе счисления. Запись обоих имеет длину n. Вы можете сколько угодно раз менять две соседние цифры местами в любом из чисел. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся после применения таких перестановок числам?

Эта операция определена над двоичным представлением чисел.

Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): xk-1...x2x1x0 и yk-1...y2y1y0. Здесь xi это i-й бит числа x, а yi это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет rk-1...r2r1r0, где:  

\(r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases}\)

В первой строке содержится одно целое число n (1 <= n <= 100000) - длина записи чисел. Во второй строке задана запись числа a. В третьей строке задана запись числа b.

Буквы A, B, C, D, E, F отвечают за цифры 10, 11, 12, 13, 14, 15 в шестнадцатеричной системе счисления соответсвенно. Записи могут содержать ведущие нули.

В единственной строке вам необходимо вывести одно шестнадцатеричное число длины n, которое является ответом на вопрос из условия.

В первом примере можно поменять две соседние цифры в первом числе, получится F0 XOR 0E = FE.

Во втором примере любая перестановка цифр не меняет a  XOR  b. Обратите внимание, что длина выводимого числа должна быть равна n, поэтому надо выводить лидирующие нули.

В третьем примере можно получить 101010 из a и 010100 из b.

Примеры

2
0F
0E

FE

3
000
000

000

6
010110
011000

111110

2^k

Напишите программу, которая по заданному числу k (0 <= k <= 31) выводит на экран число 2k, то есть число, у которого k-й бит равен 1, а остальные - нули.

В программе нельзя использовать арифметические операции, необходимо использовать только битовые операции!
 

Примеры

Установите бит

Напишите программу, которая устанавливает 1 в k-й бит числа  N. Выведите на экран полученное число.

В программе нельзя использовать арифметические операции, необходимо использовать только битовые операции!
 

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

Дано целое число N и натуральное число k.

Выведите на экран число, полученное после установки в 1 заданного бита.

Примеры

Сбросить бит

Напишите программу, которая сбрасывает (устанавливает 0) k-й бит числа  N. Выведите на экран полученное число.

В программе нельзя использовать арифметические операции, необходимо использовать только битовые операции!
 

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

Дано целое число N (N<109) и натуральное число k (k<109).

Выведите на экран число, полученное после сбрасывания заданного бита.

Примеры

Определите значение бита

Напишите программу, которая определяет значение k-го бита числа  N. 

В программе нельзя использовать арифметические операции, необходимо использовать только битовые операции!
 

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

Дано целое число N и натуральное число k.

Выведите на экран значение заданного бита (0 или 1).

Примеры

Быстрое умножение

Даны числа a и b. Не используя операции *, /, //, % вычислите их произведение.
 

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

Даны два числа a и b.

Выведите произведение чисел a и b.

Примеры

Сбросить младшую единицу

Дано число, сбросьте младший ненулевой бит (т.е. первую справа единицу замените на ноль).

Запрещается использовать ветвления и циклы. 
 

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

Одно неотрицательное число a.

Выведите результирующее число.

Примеры

Сумма элементов с k битами в индексе

Когда-то давно, в мире чисел произошло необычное событие. Числа начали обретать новое свойство - свойство "установленных битов". Если представить число в двоичной системе, то установленные биты - это цифры, которые равны единице.
Ваш задача заключается в том, чтобы подсчитать сумму элементов в массиве nums, чьи индексы содержат ровно k таких установленных битов. 

Входные данные
Программа получает на вход в первой строке число n - количество элементов в массиве nums. Во второй строке записаны n чисел numsi - элементы массива. В третьей строке записано число k.
 

Ограничения:

• 1 <= n <= 1000
• 1 <= nums[i] <= 105
• 0 <= k <= 10
• 0 <= i < n

Примеры

5
5 10 1 5 2
1

13

4
4 3 2 1
2

1

Расстояние Хэмминга между двумя числами

Расстояние Хэмминга между двумя целыми числами - это количество позиций, в которых соответствующие биты различаются.
Для заданных двух целых чисел x и y, найдите расстояние Хэмминга между ними.

Входные данные
Программа получает на вход два целых числа x и y. Каждое число записано в отдельной строке.
 

Ограничения

• 0 <= x, y <= 231 - 1

Примеры

1
4

2

1   (0 0 0 1)
4   (0 1 0 0)

Игра с таблицей

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

• выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);

• выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

Формат входных данных

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

• В первой строке выведите строку <<YES>>.

• Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).

• В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел \(5\) из исходной.

В третьем примере изначально дана таблица:

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

Электронные часы

Циферблат новых электронных часов, установленных на главном здании офиса фирмы Macrohard, состоит из 4 прямоугольных панелей, каждая из которых состоит из 6 рядов по 5 лампочек в каждом. Первые две панели отображают цифры, из которых складываются часы, а следующие две - минуты. (Если сейчас меньше 10 часов, первая панель отображает 0).

К сожалению, лампочки, установленные на панелях, были произведены компанией Sveta.Net, которая известна своим принципом , вследствие чего на следующий день люди, проходя мимо офиса компании, видели лишь некоторое подобие цифр, поскольку некоторые лампочки больше не горели.

Петя живет в доме, стоящем прямо напротив офиса компании Macrohard. В первый день после установки часов он зарисовал у себя в блокноте, как выглядят все цифры на панелях (панели однотипные, поэтому одна и та же цифра на различных панелях выглядит одинаково). Теперь Петя хочет узнать, можно ли по текущему изображению на часах однозначно определить, сколько сейчас времени. Помогите ему!

Входные данные
Входные данные содержат 6 строк по 20 символов в каждой - текущее изображение на часах. Первый прямоугольник задает первую панель, следующий - вторую, следующий - третью и последний - четвертую.

Выходные данные
Если можно точно определить время, которое сейчас отображается на часах, выведите это время в формате hh:mm. Если время нельзя определить однозначно, выведите AMBIGUITY. Если же в часах точно сломалось еще что-то, например, центральный процессор, который управляет лампочками, выведите ERROR.

Установить единицы

Напишите программу, заменяющую с \(k\)-го по \(l\)-й (включительно) биты числа \(n\) на единицы. Нумерация бит ведётся справа налево, начиная с нуля.

Формат входных данных

На ввод в одной строке через пробел подаются три целых числа: \(n\), \(k\), \(l\).

Гарантируется, что \(0\leqslant n<2^{31}\), \(0\leqslant k\leqslant l\leqslant 30\).

Формат выходных данных

Программа должна вывести число, полученное после описанной выше замены бит в числе \(n\).

Замечание

В приведённом примере число 34 представляется в двоичном виде как 100010. Установив в 1 биты с первого по третий, получим 101110, что является двоичным кодом числа 46.

Переключить биты

Напишите программу, переключающую с \(k\)-го по \(l\)-й (включительно) биты числа \(n\). Нумерация бит ведётся справа налево, начиная с нуля.

Формат входных данных

На ввод в одной строке через пробел подаются три целых числа: \(n\), \(k\), \(l\).

Гарантируется, что \(0\leqslant n<2^{31}\), \(0\leqslant k\leqslant l\leqslant 30\).

Формат выходных данных

Программа должна вывести число, полученное после описанной выше замены бит в числе \(n\).

Замечание

В приведённом примере число 34 представляется в двоичном виде как 100010. Переключив биты с первого по третий, получим 101100, что является двоичным кодом числа 44.

Кодовое расстояние

Определите кодовое расстояние между двумя двоичными кодами длины D

Входные данные
Сначала вводится число D – длина кодов (целое, положительное, не превышает 100), затем вводятся два кода, каждый в своей строке.

Выходные данные
Выведите одно число –расстояние между этими кодами.

Учитель математики Юрий Петрович

RAID

Кодовый замок

Весь год Гошан был прилежным мальчиком и делал добрые дела: переводил бабушку через дорогу, еженедельно оставался в школе на контесты, давал одноклассникам списать химию и т.д.  За это Дедушка Мороз позволил Гошану выбрать абсолютно любой подарок на новый год. Гошан воспользовался возможностью и попросил долгожданную для него книгу “History of Hip-Hop”, ведь он был истинным поклонником хип-хопа! За кем же еще может стоять андерграунд?

Но Дед Мороз решил устроить испытание для мальчика. Он поставил на коробку с книгой кодовый замок.
Кодовый замок устроен следующим образом. На электронном экране замка появляются три числа – a , b и c. Чтобы открыть замок необходимо перевести числа a и b в двоичную систему счисления и поразрядно выполнить для них операцию c.
Описание операций: