TRANSFER - After Party Transfers

You've been to a potluck party (party where each person contributes food), but some people are angry that they spent more money preparing their dish than the others. Now they want you (they span the bottle) to figure out how the participants of the party can, in the fewest amount of transfers, become even.

To clarify, you are free to transfer money between them in any way you like, but eventually the money they spent on their dishes, plus the money they received, minus the money the sent, must be equal for all participants.

Input

The first line contains C ∈ [0..10] - the number of test cases.

For each test case, the first line contains the number N ∈ [0..20] - the number of people at the party.

The following N lines contains a integer xi ∈ [0,10^6] representing the amount of money the ith persons dish cost.

Output

For each testcase:

The first line should be the minimal amount of transfers needed to even out the party budget.

The following lines should be on the form "a -> b: t", where a, b ∈ [0..N) and represent that person 'a' must transfer 't' money to person 'b'. t is here a floating point number of at least 6 digits precision. (Notice: that is 6 digits precision after adding together your in and out flows)

In case of multiple best solutions exists, print any.

Example

Input:
2
6
2
4
1
5
0
6
3
9
16
25

Output:
3
0 -> 1: 1.0
2 -> 3: 2.0
4 -> 5: 3.0
2
0 -> 1: 7.6666666666667
1 -> 2: 8.33333333333

Explanation:

In the first case, 3 is the minimal amount of transfers. An alternative transfer pattern would be

"0 -> 3: 1    1 -> 3: 2    2 -> 4: 2     2 -> 5: 1". That would have made everyone even, but would have taken one more transfer (4).

In the second case, after the transfers, each person is down 16.666.


Added by:Thomas Dybdahl Ahle
Date:2011-12-13
Time limit:1s-1.038s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2023-11-19 15:49:18
How is it possible to solve this under 3^n? Greedy algorithms for subsets aren't worknig here.
2016-01-02 14:21:04 Thomas Dybdahl Ahle
@Luke Pebody: Do you know why your solution times out? It looks to me, as it's doing the right thing, but it times out on a simple case with 10 instances of 20 random integers, that even my java solution solves pretty fast.
2013-04-24 11:21:56 Thomas Dybdahl Ahle
@Atul: Your program doesn't always find the smallest transfer scheme.

Last edit: 2016-01-02 14:10:14
2012-06-06 13:59:09 Thomas Dybdahl Ahle
kostya: You seam to sometimes output the wrong 'number of transfers' number, even though you then output the correct transfer lines.
2012-02-04 00:58:14 Thomas Dybdahl Ahle
@Linguo and @LeppyR64: You both need 2 more digits of precision, then you should be fine.
@Lewin Gan: You fail on "1 15 913 856 998 113 159 510 443 334 503 934 125 596 671 154 644"
2011-12-15 13:49:17 Thomas Dybdahl Ahle
Sorry guys, there was a mistake in the judge, so it would give the wrong return code on some wrong output. I've rejudged your last submissions.
2011-12-15 13:49:17 Luke Pebody
Why is my code returning a compilation error?
2011-12-15 13:49:17 LeppyR64
Why is my code returning a compilation error?
2011-12-15 13:49:17 Thomas Dybdahl Ahle
Lewin: Your solution is failing because it does not always find the optimal solution. A simple example is "3, 4, 0, 1" where it uses 3 transfers instead of 2.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.