Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

2^k#44570

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

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

Примеры

№	Входные данные	Выходные данные
1	5	32

Битовые операции

✓ 115✗ 80200лёгкаяВойти и решать

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

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

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

Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): x_k-1...x₂x₁x₀и y_k-1...y₂y₁y₀. Здесь x_i это i-й бит числа x, а y_i это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет r_k-1...r₂r₁r₀, где:

\(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.

Примеры

№	Входные данные	Выходные данные
1	2 0F 0E	FE
2	3 000 000	000
3	6 010110 011000	111110

Битовые операции

✓ 6✗ 71 200средняяВойти и решать

Волшебник ORZ#44389

Волшебник ORZ любит колдовать над числами. Вы решили проверить его силу и дали ему массив a, состоящий из n целых чисел, а также целое число z. Нумерация элементов массива начинается с 1.

Волшебник ORZ проделывает следующую операцию любое количество (возможно, ноль) раз:

Он выбирает целое число i, такое что 1<= i <= n. Затем он шепчет заклинание и после этого одновременно число a_i превращается в число равное (a_i or z), а число z превращается в число, равное (a_iand z).

Здесь or и and обозначают операции побитового ИЛИ и побитового И соответственно.

Найдите максимально возможное значение максимального элемента в массиве a после некоторого (возможно, нулевого) количества превращений.

Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 2³⁰). Вторая строка набора входных данных содержит n целых чисел: a₁, a₂,...,a_n (0 <= a_i< 2³⁰). Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 10⁴.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Примечание
1	2 3 3 4	7	Одной из оптимальных последовательностей действий является следующая: Выполнить операцию для `i = 1`. Теперь a1 становится равным `(3 or 3) = 3`, а `z` становится равным `(3 and 3) = 3`. Выполнить операцию для `i = 2`. Теперь a2 становится равным `(4 or 3) = 7`,, а z становится равным `(3 and 3) = 0`. Выполнить операцию для `i = 1`. Теперь a1 становится равным `(3 or 0) = 3`, а z становится равным `(3 and 0) = 0`. После этих операций последовательность a становится равной `[3,7]`, и максимальное значение в ней равно 7. Можно доказать, что максимальное значение в a не может превосходить 7 ни при какой последовательности операций, так что ответ равен 7.
2	5 5 0 2 4 6 8	13

Битовые операции

✓ 19✗ 36800средняяВойти и решать

XOR мешанина#44387

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 4 3 2 5	2

Битовые операции

✓ 38✗ 64500лёгкаяВойти и решать

И Ка#44386

Громозека изучает битовые операции. Сегодня он изучит побитовую операцию И (&). Теперь ему стало интересно, при каком наибольшем целом значении k будет выполняться условие, записанное ниже.

x & (x - 1) & (x - 2) & ... & k = 0

Входные данные
Первая строка входных данных содержит целое число t (1 <= t <= 3*10⁴) - количество целых чисел x, для которых необходимо найти ответ. Далее программа получает t строк, в каждой из которых записано по одному целому числу x (1<= x <= 10⁹).

Выходные данные
Для каждого значения x в отдельной строке выведите наибольшее целое значение k, при котором будет выполняться условие задачи.

Примеры

№	Входные данные	Выходные данные
1	3 2 5 17	1 3 15

Битовые операции

✓ 36✗ 77500лёгкаяВойти и решать

Мир XOR#39385

Пусть \(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).

Примеры

№	Входные данные	Выходные данные
1	2 4	5
2	123 456	435
3	123456789012 123456789012	123456789012

Битовые операции

✓ 8✗ 941 100средняяВойти и решать

XOR и сумма#38518

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

Битовые операции Динамическое программирование Рекурсия

✓ 1✗ 1—Войти и решать

Уравнения математической магии#38513

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: a−(a⊕x)−x=0 для заданного a, где знаком ⊕ обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю 2³². Ойра-Ойра быстро нашел x, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю 2³², Кристобаля Хунту интересует количество таких решений x, что 0 ≤ x ≤ 2³². Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные
В первой строке задано одно целое число a (0 ≤ a ≤ 2³²−1).

Выходные данные
Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа x и y, рассмотрим их двоичные записи (возможно с ведущими нулями): x_k...x₂x₁x₀ и y_k...y₂y₁y₀. Здесь x_i это i-й бит числа x, а y_i это i-й бит числа y. Пусть r=x⊕y — результат операции XOR над числами x и y. Тогда двоичной записью r будет r_k...r₂r₁r₀, где:

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

В первом примере решениями уравнения являются 0 и 2147483648=2³¹, так как 0−(0⊕0)−0=0−0−0=0 и 0−(0⊕ 2147483648)−2147483648=−4294967296=−2³²=0 по модулю 2³².

Во втором примере решениями уравнения являются 0, 2, 2147483648=2³¹ и 2147483650=2³¹+2.

В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 2³².

Примеры

№	Входные данные	Выходные данные
1	0	2
2	2	4
3	4294967295	4294967296

Битовые операции Разбор случаев

✓ 2✗ 0—Войти и решать

Двоичные строки заданной длины в обратном порядке#34957

По данному числу N выведите все строки длины N из нулей и единиц в обратном лексикографическом порядке.

В решении задачи использовать перебор всех подмасок.

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

Задано единственное число N. (1 ≤ N ≤ 10)

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

Необходимо вывести все строки длины N из нулей и единиц в обратном лексикографическом порядке.

Ввод	Вывод
2	11 10 01 00

Битовые операции

✓ 62✗ 25400лёгкаяВойти и решать

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

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

В решении задачи использовать перебор всех подмасок.

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

Задано единственное число N. (натуральное, 1 ≤ N ≤ 10)

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

Необходимо вывести все строки длины N из нулей и единиц в лексикографическом порядке, по одной на строке

Ввод	Вывод
2	00 01 10 11

Битовые операции

✓ 75✗ 43500лёгкаяВойти и решать

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

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число \(19_{10} = 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0 \) в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

...
и результатом игры, следовательно, окажется число \(1\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0 = 28_{10} \)

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

Решите эту задачу с использованием битовых операций!

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

Входной файл содержит одно целое число N (0<=N<=32767).

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

Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.

Примеры

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

Битовые операции Двоичная система счисления

✓ 132✗ 276800средняяВойти и решать

2^n+2^m#34915

Найдите сумму двух различных степеней числа 2, используя только битовые операции. В частности нельзя использовать операцию сложения чисел.

Входные данные: Даны два неравных числа: n и m, не превосходящие 31.
Выходные данные: Выведите на экран значение суммы 2ⁿ+2^m.

Примеры

№	Входные данные	Выходные данные
1	1 2	6

Битовые операции

✓ 434✗ 431400лёгкаяВойти и решать

Обнулить последние биты#34914

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 1	4

Битовые операции

✓ 430✗ 690400лёгкаяВойти и решать

Тихий Дон №1#29641

В мирное время казаки занимаются сельским хозяйством. Пантелей Прокофьевич Мелехов выращивает специальные математические овощи, которые растут по очень странным правилам: у каждого семечка i этих овощей есть значение урожайности ai, а урожайностью всей грядки является произведение урожайностей всех семян, посаженных на ней. У Мелехова есть N семян. Помогите ему выбрать из этих семян несколько так, чтобы при посадке этих семян урожайность грядки была максимальна.

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

В первой строке содержится число N (1 <= N <= 15)

Во второй - N чисел ai, возможно вещественных (|ai| < 10)

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

Выведите максимальную урожайность грядки с точностью не менее 6 знаков после запятой, которой можно добиться с данным набором семян. Гарантируется, что оно больше 1.

Ввод	Вывод
5 2.0 -1.2 4.7 -2.9 -1.1	32.712000

(с) Григорьев Е., 2018

Битовые операции

✓ 52✗ 93600лёгкаяВойти и решать

RAID#28422

При хранении данных одна из основных задач – соблюдение баланса между расходами на количество дисков и надёжностью записи. Одним из компромиссных по надёжности и стоимости хранения данных является RAID-3 – избыточный массив независимых дисков с выделенным диском для хранения блоков чётности. Наш RAID-3 состоит из пяти дисков, на четырёх из которых содержится информация, а на пятом – блоки контрольных битов чётности. При записи четырёх байтов (по байту на каждый из четырёх дисков) вычисляется контрольный байт четности, составленный из контрольных битов. Для каждого из восьми разрядов вычисляется сумма значений битов в этих разрядах во всех байтах данных, при этом значение контрольного бита выбирается так, чтобы сумма значений во всех разрядах (включая контрольный) была чётной. Например, у нас есть два основных диска и на них записывается байты 10010010 и 01110111. Тогда значение контрольного байта равно 11100101 – в каждом разряде сумма получается чётной.

Один из четырёх основных дисков в RAID-3 вышел из строя. Известны значения байтов в трёх оставшихся дисках и значение байта на контрольном диске. Какой байт был записан на сломавшемся диске? Все числа приведены в десятичной системе счисления.

– значения на первых трех дисках: 177, 177, 177, контрольный байт: 177;

– значения на первых трех дисках: 79, 79, 79, контрольный байт: 0;

– значения на первых трех дисках: 46, 56, 248, контрольный байт: 90;

– значения на первых трех дисках: 255, 0, 150, контрольный байт 96;

– значения на первых трех дисках: 137, 232, 23, контрольный байт 212.

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

пробелом.

Битовые операции Вывод формулы

✓ 0✗ 11 000средняяВойти и решать

Задача №2#24632

int main()
{
       string s;
       vector <int> arr = { 70, 109, 108, 96, 37, 100, 114, 113, 41, 56, 96, 61, 59 };
       for(int i = 0; i < arr.size(); i++)
       {
             int x = s[i];
             cout << (x ^ arr[i]) << " ";
       }
       return 0;
}

Какое значение должна принимать строка s, чтобы в результате выполнения программы было выведено

1 2 3 4 5 6 7 8 9 10 11 12 13

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

Входные данные пусты

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

Выведите одну строку – ответ на задачу.

(c) Егор Курбатов, 10и

Битовые операции Целые числа

✓ 0✗ 261 300средняяВойти и решать

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

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

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

1	Конъюнкция
2	Дизъюнкция
3	Исключающее или
4	Импликация
5	Эквивалентность

Результат операции необходимо представить в виде числа в двоичной системе счисления, а затем перевести в десятичное число .
Это число и будет являться ключом числа.
Помогите Гошану открыть замок, ведь с логикой у него плохи дела, а ему очень хочется поскорее почитать “History of Hip-Hop”.
P.S. Если в одном из чисел a и b разрядов будет больше, чем в другом, то в наименьшее необходимо добавить ведущие нули.
Входные данные
Входной файл содержит в себе три числа – a,b(1<=a,b<=1000) и с(1<=c<=5).
Выходные данные
Необходимо вывести одно число – ответ на задачу.
Пример
Ввод:
12 10 5
Вывод:
9
Пояснение
12=1100
10=1010

1100

1010

1001

1001=9

(с) Курбатов Егор 9и

Битовые операции Двоичная система счисления

✓ 4✗ 111 100средняяВойти и решать

21766#21766

Дано натуральное десятичное число N (N<=255). Найдите местоположение младшего единичного бита. Выведите номер бита в десятичной системе счисления

Битовые операции Двоичная система счисления

✓ 60✗ 242700средняяВойти и решать