F - Candy Redistribution 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

N 人の子供がいます。子供たちには 1 から N までの番号が付けられています。

子供 i は飴を A_i 個持っています。

あなたの目標は、以下の操作をできるだけ少ない回数実行し、最終的に N 人の子供全員が同数の飴を持っている状態にすることです。

  • 相異なる 2 人の子供 x,y を選び、子供 x が持っている飴の個数以下の正の整数 z を選ぶ。子供 x が持っている飴のうち z 個を回収し、子供 y に渡す。

最終的に N 人の子供全員が同数の飴を持っている状態になる操作列が存在するか判定してください。存在する場合は、そのうち操作回数が最小になるようなものを 1 つ求めてください。

制約

  • 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 は i 回目の操作で選ぶ x,y,z の値を表す。

解が複数存在するときは、どれを出力しても正解とみなされる。

入力例 1

4
1 7 4 8

出力例 1

3
2 3 1
2 4 1
4 1 4

この出力例では、以下のように操作が実行されます。

  1. 子供 2 から飴を 1 個回収し、子供 3 に渡す。この直後、各子供が持つ飴の個数は 1,6,5,8 になっている。
  2. 子供 2 から飴を 1 個回収し、子供 4 に渡す。この直後、各子供が持つ飴の個数は 1,5,5,9 になっている。
  3. 子供 4 から飴を 4 個回収し、子供 1 に渡す。この直後、各子供が持つ飴の個数は 5,5,5,5 になっている。

これによって、最終的に N 人の子供全員が飴をちょうど 5 個ずつ持っている状態になります。

入力例 2

2
100 3

出力例 2

-1

Score : 525 points

Problem Statement

There are N children, numbered 1 to N.

Child i has A_i candies.

Your goal is to execute the following operation as few times as possible so that eventually all N children have the same number of candies.

  • Choose two distinct children x,y, and choose a positive integer z not exceeding the number of candies child x has. Take z candies from child x and give them to child y.

Determine whether there exists a sequence of operations such that eventually all N children have the same number of candies. If it exists, find one such sequence with the minimum number of operations.

Constraints

  • 2 \leq N \leq 20
  • 1 \leq A_i \leq 10^8
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 \dots A_N

Output

If there is no sequence of operations such that eventually all N children have the same number of candies, output -1.

If it exists, output one with the minimum number of operations in the following format:

q
x_1 y_1 z_1
\vdots
x_q y_q z_q

Here, q represents the number of operations, and x_i,y_i,z_i represent the values of x,y,z chosen in the i-th operation.

If there are multiple solutions, outputting any of them will be considered correct.

Sample Input 1

4
1 7 4 8

Sample Output 1

3
2 3 1
2 4 1
4 1 4

In this sample output, the operations are executed as follows:

  1. Take 1 candy from child 2 and give it to child 3. Immediately after this, the number of candies each child has is 1,6,5,8.
  2. Take 1 candy from child 2 and give it to child 4. Immediately after this, the number of candies each child has is 1,5,5,9.
  3. Take 4 candies from child 4 and give them to child 1. Immediately after this, the number of candies each child has is 5,5,5,5.

Eventually, all N children have exactly five candies each.

Sample Input 2

2
100 3

Sample Output 2

-1