PAYBACK - Byteland Money Exchange
In Byteland after the food shortage banks made credit payment freely available. At the end of the year companies have to settle their debts and to give a statement on their cashflow to the Claim Office. Among Banks and Companies a net of debts was created. Unfortunetely Banks gave a sky-high price on money transfers. For company owners it was unprofitable to pay all money transfers as they were. They chose you to help them out. Your assignment is to balance the debt network.
You are given [t<=1000] test cases- a test case consists of the size [N<=1000] of the debt network, followed by a description of the network itself. Each line consists of integers separated by spaces ending with a new line. Each value states how much money the company in line "i" is in debt to company "j" where "j" is the column number.
Your assignment is to limit the number of money transfers by determining which companies are in debt, which have earned money and which have shown neither profit nor loss.
Input
t [- test cases]
N [- size of the debt net]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next test case]
a graphical example
Output
T[Size of solution]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next solution]
Text grouped in [ ] does not appear in the input file.
a graphical example
a graphical example- same input
Example
Input: 1 7 0 18 25 34 14 21 40 44 0 64 0 11 5 24 11 35 0 23 17 26 23 19 50 20 0 16 7 0 0 14 9 0 0 27 18 42 5 17 8 3 0 17 36 26 0 47 7 6 0 Output: 7 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 6 3 0 0 0 0 0 0 59 0 0 0 0 0 0 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0
hide comments
deepesh17feb:
2015-01-11 15:49:50
total amount after calculate[cred - debt] comes out to be zero for each,please reply |
|
Sylwester Herber:
2013-08-12 08:59:24
@Imre Palik - Would you mind to elaborate? |
|
Imre Palik:
2009-06-11 16:10:25
The sample output is wrong. |
Added by: | Sylwester Herber |
Date: | 2005-12-01 |
Time limit: | 3.221s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | inspired by "Algorithm Complexity Theory" project assignment 2002 |