Codeforces Round 651 (Div. 2) |
---|
Закончено |
У Ashish есть массив $$$a$$$, состоящий из $$$2n$$$ положительных целых чисел. Он хочет сжать массив $$$a$$$ в массив $$$b$$$ размера $$$n-1$$$. Чтобы это сделать, он сначала выбирает ровно $$$2$$$ (любые два) элемента массива $$$a$$$ и удаляет их из массива. После этого он выполняет следующую операцию, пока массив $$$a$$$ не пустой:
Получившийся массив $$$b$$$ должен удовлетворять одному условию. Наибольший общий делитель ($$$\mathrm{gcd}$$$) всех элементов массива должен быть больше $$$1$$$.
Напомним, что наибольший общий делитель ($$$\mathrm{gcd}$$$) массива положительных целых чисел равен наибольшему целому числу, которое является делителем всех элементов массива.
Можно доказать, что всегда можно таким образом сжать массив $$$a$$$ в массив $$$b$$$ размера $$$n-1$$$, так что $$$gcd(b_1, b_2..., b_{n-1}) > 1$$$.
Помогите Ashish найти способ это сделать.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10$$$) — количество наборов входных данных. Описание наборов входных данных следует.
В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$2 \leq n \leq 1000$$$).
Во второй строке описания каждого набора входных данных находится $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 1000$$$) — элементы массива $$$a$$$.
Для каждого набора входных данных, выведите $$$n-1$$$ строку — выполненные операции, чтобы сжать массив $$$a$$$ в массив $$$b$$$. Изначальное удаление двух элементов не является операцией и про это действие не нужно ничего выводить.
В $$$i$$$-й из этих строк должно находиться два целых числа, индексы (нумерация с $$$1$$$) двух элементов массива $$$a$$$, которые используются в $$$i$$$-й операции. Все $$$2n-2$$$ выведенных индекса должны быть различными целыми числами от $$$1$$$ до $$$2n$$$.
Вам не нужно выводить индексы двух изначально удаленных элементов из массива $$$a$$$.
Если есть несколько возможных ответов, вы можете найти любой.
3 3 1 2 3 4 5 6 2 5 7 9 10 5 1 3 3 4 5 90 100 101 2 3
3 6 4 5 3 4 1 9 2 3 4 5 6 10
В первом наборе входных данных $$$b = \{3+6, 4+5\} = \{9, 9\}$$$ и $$$\mathrm{gcd}(9, 9) = 9$$$.
Во втором наборе входных данных $$$b = \{9+10\} = \{19\}$$$ и $$$\mathrm{gcd}(19) = 19$$$.
В третьем наборе входных данных $$$b = \{1+2, 3+3, 4+5, 90+3\} = \{3, 6, 9, 93\}$$$ и $$$\mathrm{gcd}(3, 6, 9, 93) = 3$$$.
Название |
---|