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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 34956. Двоичные строки заданной длины
Темы: Битовые операции   

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

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

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

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

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

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

Ввод Вывод 
2
 
00
01
10
11
 
ID 34957. Двоичные строки заданной длины в обратном порядке
Темы: Битовые операции   

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

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

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

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

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

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

Ввод Вывод
2 
11
10
01
00
 
ID 29641. Тихий Дон №1
Темы: Битовые операции   

В мирное время казаки занимаются сельским хозяйством. Пантелей Прокофьевич Мелехов выращивает специальные математические овощи, которые растут по очень странным правилам: у каждого семечка 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
ID 38513. Уравнения математической магии
Темы: Разбор случаев    Битовые операции   

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

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

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

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

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

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

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

В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 232.
 
Примеры
№ Входные данные Выходные данные
1 0 2
2 2 4
3 4294967295 4294967296

ID 39385. Мир 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 <= 1012).

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

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

ID 44386. И Ка
Темы: Битовые операции   

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

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

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

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

ID 44387. XOR мешанина
Темы: Битовые операции   

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 4
4 3 2 5		 2

ID 44389. Волшебник ORZ
Темы: Битовые операции   

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

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

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


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

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


Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 230). Вторая строка набора входных данных содержит n целых чисел: a1, a2,...,an (0 <= ai < 230). Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 104.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
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  

ID 44507. Максимальный 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.

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

ID 34915. 2^n+2^m
Темы: Битовые операции   

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

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

Примеры
№ Входные данные Выходные данные
1 1 2 6

ID 44570. 2^k
Темы: Битовые операции   

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

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

Примеры
№ Входные данные Выходные данные
1 5 32

ID 44571. Минимальная OR сумма
Темы: Битовые операции   

Громозека записал на листочек 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<=230).


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

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



Примеры
№ Входные данные Выходные данные
1 
3
1 3 2
 
3
2 
5
1 2 4 8 16
 
31
3 
2
6 6
 
6
4 
3
3 5 6
 
7
 
ID 44572. Установите бит
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 1 7
 
 
ID 44573. Инвертируйте бит
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 2 1
 

 
ID 44574. Сбросить бит
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 2 1
 


 
ID 44575. Сбросить все биты, кроме последних
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 1 1
 


 
ID 44576. Определите значение бита
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 1 0
 


 
ID 44577. Байт побитно
Темы: Битовые операции   

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 
5
 
00000101
 


 
ID 44578. Быстрое умножение
Темы: Битовые операции   

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 5 2 10

ID 44579. Установите младший нулевой бит
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 0 1
2 5 7

ID 44580. Сбросить младшую единицу
Темы: Битовые операции   

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

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

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

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


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

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

 

Примеры
№ Входные данные Выходные данные
1 1 0
2 5 4
 
ID 44583. Максимальный XOR
Темы: Битовые операции   

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

 

Примеры
№ Входные данные Выходные данные
1 
2
00|11
00|10
 
11|10
2 
3
00|00|00
00|00|00
 
00|00|00
3 
3
10|10|01
00|01|01
 
11|11|01

ID 47283. Сумма элементов с k битами в индексе
Темы: Битовые операции   

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

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

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

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


Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 
5
5 10 1 5 2
1
 
13
2 
4
4 3 2 1
2

1

ID 47285. Декодируй массив
Темы: Битовые операции   

Магистр Максимус создал массив из n неотрицательных целых чисел, но чтобы сохранить его в тайне, он преобразовал его в другой массив encoded длиной n-1. Каждый элемент encodedi был получен путем выполнения операции XOR над двумя соседними элементами arr[i] и arr[i+1]. Например, если исходный массив arr = [1,0,2,1], то полученный массив encoded = [1,2,3].

Теперь Магистр Максимус хочет передать эту тайну другому волшебнику, но ему нужно вернуться к исходному массиву arr. Однако у него есть подсказка - первый элемент arr равен first.

Помогите Магистру Максимусу восстановить исходный массив arr! Мы уверены, что ответ существует и является уникальным. Расшифруйте тайну и восстановите массив arr.



Входные данные
Программа получает на вход в первой строке число n - количество элементов исходного массива. Вторая строка содержит n-1 число encodedi - элементы закодированного массива. 
 

Ограничения

  • 2 <= n <= 104
  • Длина массива encoded == n - 1
  • 0 <= encodedi <= 105
  • 0 <= first <= 105


Выходные данные
Выведите n чисел в однй строку через пробел - элементы исходного массива arr.
 
 
Примеры
№ Входные данные Выходные данные
1 
4 
1 2 3 
1
 
1 0 2 1
2 
5
6 2 7 3
4

4 2 0 7 4

ID 47349. Расстояние Хэмминга между двумя числами
Темы: Битовые операции   

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

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

Ограничения

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

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
1
4
 
2
 
1   (0 0 0 1)
4   (0 1 0 0)

ID 47351. Внутреннее представление целого числа в шестнадцатеричном формате
Темы: Битовые операции   

Для заданного целого числа со знаком num найдите его внутренее представление в памяти компьютера в шестнадцатеричной системе счисления (в 32-разрядной сетке).

Входные данные
Программа получает на вход целое число num (-231 <= num <= 231 - 1).

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

Примеры
№ Входные данные Выходные данные
1 
26
 
1a
2 
-1
 
ffffffff


 
ID 48967. Игра с таблицей
Темы: meet in the middle    Битовые операции   

Дана таблица \(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}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

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

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

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

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

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

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

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

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

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)
ID 38518. XOR и сумма
Темы: Битовые операции    Рекурсия    Динамическое программирование   

Вам дано положительное целое число 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  

 
ID 54669. Электронные часы
Темы: Битовые операции    Двумерные массивы    Дата и время   

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

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

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

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

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