Codeforces Round 939 (Div. 2) |
---|
Закончено |
У Нины есть матрица $$$a$$$ размера $$$n\times n$$$, заполненная нулями. $$$j$$$-й элемент $$$i$$$-й строки матрицы $$$a$$$ обозначается как $$$a_{i, j}$$$.
Она может выполнять операции двух типов с этой матрицей:
Нина хочет максимизировать сумму всех чисел в матрице $$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$$$. Она просит вас найти способ выполнить операции так, чтобы эта сумма была максимальной. Поскольку она не хочет выполнять слишком много операций, вы должны предоставить решение с не более чем $$$2n$$$ операциями.
Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.
В единственной строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — размер матрицы $$$a$$$.
Гарантируется, что сумма $$$n^2$$$ по всем тестовым случаям не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных на первой строке выведите два целых числа $$$s$$$ и $$$m$$$ ($$$0\leq m\leq 2n$$$) — максимальную сумму чисел в матрице и количество операций в вашем решении.
В $$$k$$$-й из следующих $$$m$$$ строк выведите описание $$$k$$$-й операции:
Обратите внимание, что вам не нужно минимизировать количество использованных операций, вам просто нужно использовать не более чем $$$2n$$$ операций. Можно показать, что максимальная возможная сумма всегда может быть получена не более чем за $$$2n$$$ операций.
212
1 1 1 1 1 7 3 1 1 1 2 1 2 1 2 2 1 1 2
В первом наборе входных данных максимальная сумма $$$s=1$$$ может быть получена за $$$1$$$ операцию присвоением $$$a_{1, 1}:=1$$$.
Во втором наборе входных данных максимальная сумма $$$s=7$$$ может быть получена за $$$3$$$ операции следующим образом:
Можно показать, что невозможно сделать сумму чисел в матрице большей $$$7$$$.
Название |
---|