← 返回题目列表

AtCoder · abc432_f

F. 糖果重新分配

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

分数: 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. 采取 1 孩子的糖果 2 并将其交给孩子 3。紧接着,每个孩子拥有的糖果数量为 1,6,5,8.
  2. 采取 1 孩子的糖果 2 并将其交给孩子 4。紧接着,每个孩子拥有的糖果数量为 1,5,5,9.
  3. 采取 4 孩子的糖果 4 并将它们交给孩子 1。紧接着,每个孩子拥有的糖果数量为 5,5,5,5.

最终,所有 N 孩子们每人正好有五颗糖果。


示例输入 2

2
100 3

示例输出 2

-1