Олимпиадный тренинг

Задача . Волшебник 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 целых чисел: a1a2,...,an (0 <= a< 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  



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python19
Комментарий учителя