Информатика

Два числа a и b записаны в двоичной системе счисления. Запись обоих имеет длину 2n. Обе записи разбиты на n блоков по 2 стоящие рядом цифры. В каждом из чисел вы можете сколько угодно раз менять два произвольных блока местами. Какое максимальное значение может быть у результата применения побитовой операции 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.

Для удобства блоки разделены символом «|».

В единственной строке вам необходимо вывести одно двоичное число из n блоков, которое является ответом на задачу, в таком же блочном формате, в каком заданы числа a и b.

В первом примере можно поменять два соседних блока в первом числе, получится 11|00  XOR  00|10=11|10.

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

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

Примеры

2
00|11
00|10

11|10

3
00|00|00
00|00|00

00|00|00

3
10|10|01
00|01|01

11|11|01

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, на проезде на парковку университета установлен шлагбаум, поэтому скорость автомобиля после того, как он проехал ровно d метров должна быть равна 0.

Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом тесте из условия Глебу выгодно действовать следующим образом:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.

3. Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

Во втором тесте из условия Глебу выгодно действовать, например, так:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

    

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

Примеры

2

3

10

7

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

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

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

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

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

Примеры

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

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

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

На вход программа получает неотрицательное число a.

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

Примеры

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

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

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

Примеры

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

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

Дано целое число N (0 <= N <= 255).

Выведите число  N в битовой форме: 8 бит, старшие биты слева, младшие – справа.

Примеры

5

00000101

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

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

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

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

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

Примеры

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

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

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

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

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

Примеры

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

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

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

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

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

Примеры

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

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

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

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

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

Примеры

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

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

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

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

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

Примеры

Громозека записал на листочек n чисел ai. Затем он выполняет над массивом следующую операцию

• выбирает два различных целых числа i, j (1 <= i < j <= n) и заменяет ai на x и aj на y. Чтобы не нарушать массив, Громозека следить чтобы выполнялось условия ai|aj=x|y, где | обозначает побитовое ИЛИ. Заметьте, что x и y это целые неотрицательные числа.

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

Первая строка  входных данных содержит целое число n (2 <= n <= 100) -  количество чисел, которые записал Громоезка на листочке. Вторая строка входных данных содержит n целых чисел a1,a2,…,an (0<=ai<=2³⁰).

Выведите минимальную возможную сумму массива.

Примеры

3
1 3 2

3

5
1 2 4 8 16

31

2
6 6

6

3
3 5 6

7

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

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

Примеры

Два числа 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

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, у проезда на парковку университета установлен датчик движения: если скорость проезжающего транспортного средства будет превышать s, то администрация университета выпишет нарушителю дисциплинарное взыскание. Конечно, Глеб не хочет его получить, поэтому при въезде в университет, когда автомобиль проехал все d метров его скорость x должна быть не больше s.

Пока Глеб собирался на работу, его заинтересовал вопрос, а за какое минимальное время он может доехать до работы, если будет действовать оптимально, но не нарушать правила при въезде в университет. Так как преподаватель будет занят скоростным вождением, ответить на этот вопрос честь выпала вам!

В двух строках заданы два целых числа - d, s (1 <= d <= 10¹⁸, 0 <= s <= 10¹⁸), расстояние до университета и ограничение на конечную скорость.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом тесте из условия Глебу выгодно действовать следующим образом:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра.

    

Таким образом, он потратит 2 секунды, и его конечная скорость будет равно 1 м/с, что не превышает s.

Во втором тесте из условия Глебу выгодно действовать, например, так:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

    

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с, что не превышает s.

Примеры

2
1

2

10
0

7

Три лягушки сидят на числовой прямой в трёх различных точках с целочисленными координатами a, b, c. Лягушки боятся отступать слишком далеко друг от друга, поэтому прыгать может только одна из крайних лягушек (такая, что слева или справа от нее нет других лягушек) и только в целочисленную точку между двумя другими лягушками, если такая есть. Заметим, что в некоторых положениях ни одна из лягушек прыгнуть не может, назовем их стабильными .

Требуется по заданному начальному положению лягушек определить минимальное и максимальное число прыжков, которые могут совершить лягушки, пока не попадут в какое-нибудь стабильное положение.

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 10¹⁸), исходные позиции лягушек.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

В первом примере из условия лягушка с позиции 4 может прыгнуть на позицию 2 и образовать стабильное положение (1,2,3). Можно показать, что больше одного прыжка они сделать не смогут.

Во втором тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 10 может прыгнуть на позицию 3, тем самым придя в стабильное положение (2,3,4) за два прыжка. Можно показать, что больше 7 прыжков по описанным правилам лягушки сделать не могли.

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

В четвёртом тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 5 может прыгнуть на позицию 3, тем самым придя в положение (2,3,4) за два прыжка. Можно показать, что больше двух прыжков лягушки сделать не могли.

Примеры

1
3
4

1
1

1
10
2

2
7

1
2
3

0
0

2
1
5

2
2

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) X ∧ Y ∧ ¬Z

2) ¬X ∨ Y ∨ ¬Z

3) ¬X ∨ ¬Y ∨ Z

4) ¬X ∧ Y ∧ Z

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) X ∨ Y ∨ Z

2) ¬X ∨ ¬Y ∨ ¬Z

3) X ∧ ¬Y ∧ Z

4) ¬X ∧ ¬Y ∧ ¬Z

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) ¬X ∧ Y ∧ Z

2) X ∨ ¬Y ∨ Z

3) ¬X ∨ Y ∨ ¬Z

4) ¬X ∧ Y ∧ ¬Z