Хранители кристаллов
Просмотр в формате PDFВ древнем хранилище расположены кристаллы с номерами от 0 до n-1, где число n всегда является степенью двойки.
Нужно разбить все кристаллы на пары так, чтобы каждый кристалл попал ровно в одну пару.
Для пары кристаллов с номерами a и b их энергетический вклад равен значению побитового И:
a & b
Суммарная энергия разбиения — это сумма энергетических вкладов всех полученных пар.
Ваша задача — для каждого набора данных построить такое разбиение на пары, чтобы суммарная энергия была ровно равна k.
Если это невозможно, выведите -1.
Входные данные
В первой строке записано целое число t — количество наборов данных.
В каждой из следующих t строк записаны два целых числа n и k:
n— количество кристаллов,k— требуемая суммарная энергия.
Гарантируется, что:
4 <= n <= 2^16,nявляется степенью двойки,0 <= k <= n - 1.
Выходные данные
Для каждого набора данных:
- либо выведите
-1, если нужное разбиение не существует, - либо выведите
n / 2строк, в каждой из которых два различных целых числаaиb— кристаллы, образующие одну пару.
Каждое число от 0 до n-1 должно встретиться ровно один раз.
Если существует несколько решений, разрешается вывести любое.
Пример
Входные данные
3
4 0
4 1
4 3
Выходные данные
0 3
1 2
1 3
0 2
-1
Пояснение
В первом наборе пары (0, 3) и (1, 2) дают суммарную энергию:
(0 & 3) + (1 & 2) = 0 + 0 = 0
Во втором наборе пары (1, 3) и (0, 2) дают:
(1 & 3) + (0 & 2) = 1 + 0 = 1
В третьем наборе данных получить суммарную энергию 3 невозможно.
Комментарии
Добавьте, пожалуйста, в тестирующую систему проверку разных решений, она принимает только авторское.
ага, она в очереди на обновление