Республиканская олимпиада по информатике. 2018 год


Задача E. Na2a и уравнение

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Na2a много баловался на уроке информатики, и учитель в наказание ему придумал следующую задачу. Найти неотрицательное целое число $x$, такое что ($a_1 \oplus x) + (a_2 \oplus x) + ... + (a_n \oplus x) = S$, где $a_1,...,a_n,S$ — заданные числа. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Помогите Na2a решить данное уравнение.
Формат входного файла
В первой строке находятся два целых числа $n$, $S (1 \le n \le 10^5, 0 \le S \le 10^{12})$. Во второй строке находятся $n$ целых числа $a_1$, $a_2$, ..., $a_n(0 \le a_i \le 10^{12})$.
Формат выходного файла
Выведите -$1$, если уравнение не имеет неотрицательных решений. Иначе выведите такое $x(x \ge 0)$, что описанное в условии равенство выполняется. Если существует несколько ответов, выведите любой из них.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условии и:
  1. $n \le 1000, a_i,s \le 1000$. Оценивается в $7$ баллов.
  2. $n = 2, a_i,s \le 10^{12}$. Оценивается в $22$ баллов.
  3. $n \le 10^4, a_i,s \le 10^6$. Оценивается в $20$ баллов.
  4. $n \le 10^5, a_i,s \le 5 \cdot 10^7$. Оценивается в $16$ баллов.
  5. $n \le 10^5, a_i,s \le 10^{12}$. Оценивается в $35$ баллов.
Пример:
Вход
3 4
1 2 3
Ответ
2
\Note Таблица для исключающего ИЛИ.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Например, если $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ тогда: $X$ $\oplus$ $Y$ = $68_{10}$ = $1000100_{2}$. ( Temirlan Satylkhanov )
посмотреть в олимпиаде

Комментарий/решение:

  -1
2019-03-12 09:59:58.0 #

1 xor 1 = 0