分数: 525 点
问题陈述
有 N 儿童,已编号 1 to N.
儿童 i 有 A_i 糖果。
你的目标是尽可能少地执行以下操作,以便最终所有 N 孩子们拥有相同数量的糖果。
- 选择两个不同的孩子 x,y,并选择一个正整数 z 糖果数量不超过儿童 x 有。采取 z 孩子的糖果 x 并将它们交给孩子 y.
确定是否存在一系列操作使得最终所有 N 孩子们拥有相同数量的糖果。如果存在,请找到一个这样的具有最少操作次数的序列。
约束
- 2 \leq N \leq 20
- 1 \leq A_i \leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 \dots A_N
输出
如果没有操作序列使得最终所有 N 孩子们有相同数量的糖果,输出 -1.
如果存在,则按如下格式输出操作次数最少的一个:
q x_1 y_1 z_1 \vdots x_q y_q z_q
在这里, q 表示操作次数,并且 x_i,y_i,z_i 代表的值 x,y,z 选择于 i第次操作。
如果有多个解,输出任意一个都将被认为是正确的。
示例输入 1
4 1 7 4 8
示例输出 1
3 2 3 1 2 4 1 4 1 4
在此示例输出中,执行的操作如下:
- 采取 1 孩子的糖果 2 并将其交给孩子 3。紧接着,每个孩子拥有的糖果数量为 1,6,5,8.
- 采取 1 孩子的糖果 2 并将其交给孩子 4。紧接着,每个孩子拥有的糖果数量为 1,5,5,9.
- 采取 4 孩子的糖果 4 并将它们交给孩子 1。紧接着,每个孩子拥有的糖果数量为 5,5,5,5.
最终,所有 N 孩子们每人正好有五颗糖果。
示例输入 2
2 100 3
示例输出 2
-1