Задача №114657. Меланхолия Харухи
Харухи в очередной раз скучает. В поисках чего-то интересного она зашла в бар «Цветочки», ул. Некрасова 17 компьютерный клуб. Глава компьютерного клуба бросил ей вызов, сказав, что она не сможет решить следующее уравнение:
\(\)(x + a_1) \text{~xor~} (x + a_2) \text{~xor~} \ldots \text{~xor~} (x + a_n) = b\(\)
Даны параметры уравнения \(a_1, a_2, \ldots, a_n\) и \(b\). Требуется найти хотя бы один его неотрицательный целочисленный корень \(x\) или выяснить, что уравнение не имеет корней.
Первая строка содержит одно число \(n\) (\(1 \le n \le 1000\)).
Следующие \(n\) строк содержат по одному числу \(a_i\), записанному в двоичной системе счисления в порядке от старших разрядов к младшим.
В последней строке дано число \(b\) в таком же формате.
Гарантируется, что длины двоичных записей чисел \(a_i\) и \(b\) не превосходят \(1000\) и что числа не содержат ведущих незначащих нулей.
Если решения нет, выведите -1 .
Иначе выведите любое число \(x\), являющееся корнем, в двоичной системе счисления в формате, аналогичному формату чисел \(a_i\) и \(b\).
Длина записи не должна превосходить \(2000\) цифр и не должна содержать ведущих незначащих нулей. Можно показать, что если существует хотя бы одно решение \(x\), то существует и решение \(x\), состоящее из не более, чем \(2000\) цифр.
Напомним, что \(x \text{\bf~xor~} y\) обозначает операцию побитового исключающего « ИЛИ » чисел \(x\) и \(y\).
В первом примере уравнение имеет вид \(x + 5 = 5\), его корнем является \(0\).
Во втором примере уравнение имеет вид \(x + 5 = 6\), его корнем является \(1\).
В третьем примере уравнение имеет вид \(x + 5 = 3\), у этого уравнения нет неотрицательных целых корней.
В четвёртом примере уравнение имеет вид \((x + 5) \text{\bf~xor~} (x + 17) \text{\bf~xor~} (x + 1) \text{\bf~xor~} (x + 2) = 13\). Его корнем является \(45\) так как \((45 + 5) \text{\bf~xor~} (45 + 17) \text{\bf~xor~} (45 + 1) \text{\bf~xor~} (45 + 2) = 50 \text{\bf~xor~} 62 \text{\bf~xor~} 46 \text{\bf~xor~} 47 = 13\). Обратите внимание, что у давнного уравнения не единственный корень.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
Обозначим за \(|x|\) длину записи числа \(x\).
| Дополнительные ограничения | |||||
| Группа | Баллы | \(|a_i|\), \(|b|\) | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 21 | \(|a_i|, |b| \le 10\) | \(n \le 100\) | 0 | |
| 2 | 32 | \(|a_i|, |b| \le 50\) | \(n \le 10\) | 0 | |
| 3 | 23 | \(|a_i|, |b| \le 300\) | \(n \le 300\) | 0, 1, 2 | |
| 4 | 24 | – | – | 0, 1, 2, 3 | |
1 101 101
0
1 101 110
1
1 101 11
-1
4 101 10001 1 10 1101
101101