[UVA] 538 - Balancing Bank Accounts
Balancing Bank Accounts
| Balancing Bank Accounts |
Once upon a time there was a large team coming home from the ACM World Finals. The fifteen travellers were confronted with a big problem:
In the previous weeks, there had been many money transactions between them: Sometimes
somebody paid the entrance fees of a theme park for the others, somebody else paid the hotel room,
another one the rental car, and so on.
So now the big calculation started. Some people had paid more than others, thus the individual bank accounts had to be balanced again. "Who has to pay whom how much?", that was the question.
As such a calculation is a lot of work, we need a program now that will solve this problem next year.
Input
The input file will contain one or more test cases.
Each test case starts with a line containing two integers: the number of travellers n (
)
and the number of transactions t (
). On the next n lines the names of the travellers are
given, one per line. The names only consist of alphabetic characters and contain no whitespace. On
the following t lines, the transactions are given in the format
name1 name2 amount where name1 is
the person who gave amount dollars to name2 . The amount will always be a non-negative integer
less than 10000.
Input will be terminated by two values of 0 for n and t.
Output
For each test case, first print a line saying ``Case #i" where i is the number of the test case.Then, on the following lines, print a list of transactions that reverses the transactions given in the input, i.e. balances the accounts again. Use the same format as in the input. Print a blank line after each test case, even after the last one.
Additional restrictions:
- Your solution must consist of at most n-1 transactions.
- Amounts may not be negative, i.e. never output ``A B -20", output ``B A 20" instead.
If there is more than one solution satisfying these restrictions, anyone is fine.
Sample Input
2 1 Donald Dagobert Donald Dagobert 15 4 4 John Mary Cindy Arnold John Mary 100 John Cindy 200 Cindy Mary 40 Cindy Arnold 150 0 0
Sample Output
Case #1 Dagobert Donald 15 Case #2 Mary John 140 Cindy John 10 Arnold John 150
統計每個人總共欠了多少, 或者是 給了多少, 接著每次拿 欠最多 跟 給最多的人 出來做均分動作
#include <stdio.h>
#include <string.h>
int main() {
int n, m, i, j, c, cases = 0;
char name[20][100];
char a[100], b[100];
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
for(i = 0; i < n; i++)
scanf("%s", name[i]);
int cnt[20] = {};
while(m--) {
scanf("%s %s %d", a, b, &c);
for(i = 0; i < n; i++)
if(!strcmp(a, name[i]))
break;
cnt[i] += c;
for(i = 0; i < n; i++)
if(!strcmp(b, name[i]))
break;
cnt[i] -= c;
}
printf("Case #%d\n", ++cases);
while(1) {
int maxx = 0, minx = 0xffffff;
int idx1, idx2;
for(i = 0; i < n; i++) {
if(cnt[i] > maxx)
maxx = cnt[i], idx1 = i;
if(cnt[i] < minx)
minx = cnt[i], idx2 = i;
}
if(maxx == 0) break;
if(maxx >= -minx) {
printf("%s %s %d\n", name[idx2], name[idx1], -minx);
int tmp = -minx;
cnt[idx1] -= tmp;
cnt[idx2] += tmp;
} else {
printf("%s %s %d\n", name[idx2], name[idx1], maxx);
int tmp = maxx;
cnt[idx1] -= tmp;
cnt[idx2] += tmp;
}
}
puts("");
}
return 0;
}