Codeforces Round 896 (Div. 2) |
---|
Закончено |
Во время экзамена Reycloer встретил интересную задачу, но он не смог сразу придумать решение. Время истекает! Пожалуйста, помогите ему.
Изначально вам дан массив $$$a$$$, состоящий из $$$n \ge 2$$$ целых чисел, и вы хотите заменить все элементы в нём на $$$0$$$.
За одну операцию вы выбираете два индекса $$$l$$$ и $$$r$$$ ($$$1\le l\le r\le n$$$) и делаете следующее:
Вы можете использовать указанную выше операцию в любом порядке не более $$$8$$$ раз в общей сложности.
Найдите такую последовательность операций, что после выполнения операций в этом порядке, все элементы в $$$a$$$ станут равными $$$0$$$. Можно доказать, что решение всегда существует.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\le t\le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 100$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 100$$$) — элементы массива $$$a$$$.
Для каждого набора входных данных в первой строке выведите одно целое число $$$k$$$ ($$$0\le k\le 8$$$) — количество операций, которые вы используете.
Затем выведите $$$k$$$ строк, в $$$i$$$-й строке выведите два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$), обозначающие, что вы выбираете $$$l_i$$$ и $$$r_i$$$ в $$$i$$$-й операции.
Обратите внимание, что вам не нужно минимизировать $$$k$$$. Если существует несколько решений, вы можете вывести любое из них.
641 2 3 083 1 4 1 5 9 2 661 5 4 1 4 750 0 0 0 071 1 9 9 0 1 83100 100 0
1 1 4 2 4 7 1 8 6 1 2 3 4 5 6 1 3 4 6 1 6 0 4 1 2 6 7 3 4 6 7 1 1 2
В первом наборе входных данных, так как $$$1\oplus2\oplus3\oplus0=0$$$, после выполнения операции на отрезке $$$[1,4]$$$, все элементы в массиве станут равными $$$0$$$.
Во втором наборе входных данных после первой операции массив станет равным $$$[3,1,4,15,15,15,15,6]$$$, после второй операции массив станет равным $$$[0,0,0,0,0,0,0,0]$$$.
В третьем наборе входных данных:
Операция | $$$a$$$ до | $$$a$$$ после | |
$$$1$$$ | $$$[\underline{1,5},4,1,4,7]$$$ | $$$\rightarrow$$$ | $$$[4,4,4,1,4,7]$$$ |
$$$2$$$ | $$$[4,4,\underline{4,1},4,7]$$$ | $$$\rightarrow$$$ | $$$[4,4,5,5,4,7]$$$ |
$$$3$$$ | $$$[4,4,5,5,\underline{4,7}]$$$ | $$$\rightarrow$$$ | $$$[4,4,5,5,3,3]$$$ |
$$$4$$$ | $$$[\underline{4,4,5},5,3,3]$$$ | $$$\rightarrow$$$ | $$$[5,5,5,5,3,3]$$$ |
$$$5$$$ | $$$[5,5,5,\underline{5,3,3}]$$$ | $$$\rightarrow$$$ | $$$[5,5,5,5,5,5]$$$ |
$$$6$$$ | $$$[\underline{5,5,5,5,5,5}]$$$ | $$$\rightarrow$$$ | $$$[0,0,0,0,0,0]$$$ |
В четвертом наборе входных данных исходный массив содержит только $$$0$$$, поэтому нам не нужно выполнять никаких операций с ним.
Название |
---|