← 返回题目列表

Codeforces · 2103/E

E. 保留总和

中文机器翻译题面 查看原题

给定一个整数 $$$k$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$,其中每个元素对于所有 $$$1 \le i \le n$$$ 都满足 $$$0 \le a_i \le k$$$。您可以对阵列执行以下操作:

  • 选择两个不同的索引 $$$i$$$ 和 $$$j$$$($$$1 \le i,j \le n$$$ 和 $$$i \neq j$$$),使得 $$$a_i + a_j = k$$$。
  • 选择一个满足 $$$-a_j \le x \le a_i$$$ 的整数 $$$x$$$。
  • 将 $$$a_i$$$ 减少 $$$x$$$,将 $$$a_j$$$ 增加 $$$x$$$。换句话说,更新 $$$a_i := a_i - x$$$ 和 $$$a_j := a_j + x$$$。

请注意,对 $$$x$$$ 的约束确保数组 $$$a$$$ 的所有元素在整个操作过程中保持在 $$$0$$$ 和 $$$k$$$ 之间。

你的任务是确定是否可以使用上述操作使数组$$$a$$$非递减$$$^{\text{*}}$$$。如果可能,找到一系列最多 $$$3n$$$ 操作,将数组转换为非递减数组。

可以证明,如果通过上述操作可以使数组不减,则存在最多使用$$$3n$$$操作的解决方案。

$$$^{\text{*}}$$$ 如果对于所有 $$$1 \le i \le n - 1$$$,数组 $$$a_1, a_2, \ldots, a_n$$$ 被认为是非递减的,则它保持 $$$a_i \le a_{i+1}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$k$$$ ($$$4 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) - 数组 $$$a$$$ 的长度以及操作所需的总和。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果无法使用该操作使数组不减,则输出 $$$-1$$$。

否则,输出操作数 $$$m$$$ ($$$0 \le m \le 3n$$$)。在接下来的 $$$m$$$ 行中,输出三个整数 $$$i$$$、$$$j$$$ 和 $$$x$$$,表示 $$$a_i$$$ 减少 $$$x$$$ 且 $$$a_j$$$ 增加 $$$x$$$ 的操作。

请注意,您是 不 需要尽量减少操作次数。如果有多个解最多需要 $$$3n$$$ 操作,则可以输出任何一个。

示例

输入
复制

4
5 100
1 2 3 4 5
5 6
1 2 3 5 4
5 7
7 1 5 3 1
10 10
2 5 3 2 7 3 1 8 4 0

输出
复制

0
1
4 1 1
-1
6
1 8 2
3 5 2
5 7 3
5 9 3
8 10 5
2 10 4

注意

在第一个测试用例中,数组已经是非递减的,因此我们不需要执行任何操作。

在第二个测试用例中,我们可以执行 $$$i=4$$$、$$$j=1$$$ 和 $$$x=1$$$ 的操作。 $$$a_4$$$ 减少 $$$1$$$ 变为 $$$5 - 1 = 4$$$,而 $$$a_1$$$ 增加 $$$1$$$ 变为 $$$1 + 1 = 2$$$。运算后,数组变成$$$[2, 2, 3, 4, 4]$$$,是非减的。

请注意,还有其他方法可以使数组不递减,只要它们不使用超过 $$$3 \cdot n = 15$$$ 操作,所有这些方法都将被认为是正确的。

在第三个测试用例中,不可能使数组不减。这是因为没有不同的索引对 $$$i$$$ 和 $$$j$$$ 其中 $$$a_i + a_j = 7$$$,因此无法对数组进行任何操作。

在第四个测试用例中,数组变换如下:

  1. $$$[\textbf{0}, 5, 3, 2, 7, 3, 1, \textbf{10}, 4, 0]$$$
  2. $$$[0, 5, \textbf{1}, 2, \textbf{9}, 3, 1, 10, 4, 0]$$$
  3. $$$[0, 5, 1, 2, \textbf{6}, 3, \textbf{4}, 10, 4, 0]$$$
  4. $$$[0, 5, 1, 2, \textbf{3}, 3, 4, 10, \textbf{7}, 0]$$$
  5. $$$[0, 5, 1, 2, 3, 3, 4, \textbf{5}, 7, \textbf{5}]$$$
  6. $$$[0, \textbf{1}, 1, 2, 3, 3, 4, 5, 7, \textbf{9}]$$$