Codeforces Round 510 (Div. 2) |
---|
Закончено |
Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. С ним могут производиться следующие операции:
После каждой операции в массиве становится ровно на одно число меньше. При этом нумерация элементов сохраняется, но удалённые числа нельзя использовать в последующих операциях.
Ваша задача — произвести $$$n - 1$$$ операцию с этим массивом таким образом, чтобы единственное число, которое останется в этом массиве, было максимально возможным. Так как это число может быть достаточно большим, вместо вывода этого числа вам необходимо вывести любую последовательность действий, приводящую к максимально возможному числу. Прочитайте формат вывода для точного понимания того, что именно нужно выводить.
В первой строке входных данных следует одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве.
Во второй строке входных данных следует $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива.
Выведите $$$n - 1$$$ строку. В $$$k$$$-й строке должна содержаться одна из двух описанных операций.
Операция первого типа должна выглядеть следующим образом: $$$1~ i_k~ j_k$$$, где $$$1$$$ — тип операции, $$$i_k$$$ и $$$j_k$$$ — индексы выбранных элементов.
Операция второго типа должна выглядеть следующим образом: $$$2~ i_k$$$, где $$$2$$$ — тип операции, $$$i_k$$$ — индекс выбранного элемента. Обратите внимание, что таких операций должно быть не более одной.
Если существует несколько различных последовательностей операций, приводящих к максимальному остающемуся числу, выведите любую из них.
5
5 -2 0 1 -3
2 3
1 1 2
1 2 4
1 4 5
5
5 2 0 4 0
1 3 5
2 5
1 1 2
1 2 4
2
2 -1
2 2
4
0 -10 0 0
1 1 2
1 2 3
1 3 4
4
0 0 0 0
1 1 2
1 2 3
1 3 4
Будем обозначать за X удаленное число в массиве. Рассмотрим все тестовые примеры:
В первом тестовом примере последовательность преобразований массива может выглядеть как: $$$[5, -2, 0, 1, -3] \to [5, -2, X, 1, -3] \to [X, -10, X, 1, -3] \to$$$ $$$[X, X, X, -10, -3] \to [X, X, X, X, 30]$$$. Таким образом, максимально возможный ответ равен $$$30$$$. Обратите внимание, что другие последовательности, приводящие к ответу $$$30$$$, также допустимы.
Во втором тестовом примере последовательность преобразований массива может выглядеть как: $$$[5, 2, 0, 4, 0] \to [5, 2, X, 4, 0] \to [5, 2, X, 4, X] \to [X, 10, X, 4, X] \to$$$ $$$[X, X, X, 40, X]$$$. Также допустима, например, следующая последовательность:
1 5 3
1 4 2
1 2 1
2 3
Тогда последовательность преобразований массива будет выглядеть как: $$$[5, 2, 0, 4, 0] \to [5, 2, 0, 4, X] \to [5, 8, 0, X, X] \to [40, X, 0, X, X] \to$$$ $$$[40, X, X, X, X]$$$.
В третьем тестовом примере последовательность преобразований массива может выглядеть как: $$$[2, -1] \to [2, X]$$$.
В четвертом тестовом примере последовательность преобразований массива может выглядеть как: $$$[0, -10, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$.
В пятом тестовом примере последовательность преобразований массива может выглядеть как: $$$[0, 0, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$.
Название |
---|