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 x_{i} ∈ [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.
hide comments
kihihihi:
20231119 15:49:18
How is it possible to solve this under 3^n? Greedy algorithms for subsets aren't worknig here. 

Thomas Dybdahl Ahle:
20160102 14:21:04
@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. 

Thomas Dybdahl Ahle:
20130424 11:21:56
@Atul: Your program doesn't always find the smallest transfer scheme. Last edit: 20160102 14:10:14 

Thomas Dybdahl Ahle:
20120606 13:59:09
kostya: You seam to sometimes output the wrong 'number of transfers' number, even though you then output the correct transfer lines. 

Thomas Dybdahl Ahle:
20120204 00:58:14
@Linguo and @LeppyR64: You both need 2 more digits of precision, then you should be fine.


Thomas Dybdahl Ahle:
20111215 13:49:17
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. 

Luke Pebody:
20111215 13:49:17
Why is my code returning a compilation error? 

LeppyR64:
20111215 13:49:17
Why is my code returning a compilation error? 

Thomas Dybdahl Ahle:
20111215 13:49:17
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. 
Added by:  Thomas Dybdahl Ahle 
Date:  20111213 
Time limit:  1s1.038s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 