1. C++, Tobias Fuchs


/*
* Author: Tobias Fuchs
* Problem: 538 (Balancing Accounts)
* Verdict: Accepted
* Runtime: 0.360
*/

#include<stdio.h>
#include<vector>
#include<map>
#include<iostream>
#include<utility>
#include<string.h>
// #include<algorithm>

#ifndef _NOLOG
#define log(msg) ::std::cout << " " << msg << ::std::endl;
#else
#define log(msg) (void*)(0)
#endif

typedef struct {
int number; // own id
::std::map<unsigned int, unsigned int> debitors; // (debitor id, amount)
} debitor_t;
typedef debitor_t * debitor_p;

// ::std::map didn't work, as map can't be sorted.
// Alternative is ::std::vector< ::std::pair<unsigned int, unsigned int> >, but
// then we don't have constant time for accessing entries by id.
// So i'm using a POD struct. Eat flaming hell.
// Uber-clean solution is: Derive from ::std::map, overload iterator.next() to
// return entries ordered by account total
struct account_s {
unsigned int id;
int total;
} accounts[22];

static int account_compare_op(const void * a, const void * b) {
return ((account_s *)b)->total - ((account_s *)a)->total;
}


// List of all participants:
// Maps names (string) to ids (int)
::std::map< ::std::string, unsigned int > name_map;
::std::map< unsigned int, ::std::string > id_map;


inline unsigned int create_debitor(::std::string & name) {
unsigned int id = name_map.size();
name_map.insert( ::std::pair< ::std::string, unsigned int>(name, id));
id_map.insert( ::std::pair<unsigned int, ::std::string>(id, name));
accounts[id].id = id; // would get destroyed by later sort otherwise
accounts[id].total = 0;
return id;
}

// <id_a> owes <amount> to <id_b>
inline void add_debt(::std::string const & name_a, ::std::string const & name_b, unsigned int amount)
{
unsigned int id_a, id_b;

id_a = name_map[name_a];
id_b = name_map[name_b];
accounts[id_a].total -= amount; // increase total amount owed to id_b (creditor)
accounts[id_b].total += amount; // increase total amount owed to id_b (creditor)
}

// Transaction from id_a to id_b.
inline void print_transaction(unsigned int id_a, unsigned int id_b, unsigned int amount) {
::std::string name_a, name_b;
name_a = id_map[id_a];
name_b = id_map[id_b];
::std::cout << name_a << " " << name_b << " " << amount << ::std::endl;
}

void balance_accounts(void)
{
int c_id, d_id, subtotal, n_debitors;
n_debitors = name_map.size();

// Sort from lowest to highest account total:
::std::qsort(&accounts[0],
n_debitors,
sizeof(account_s),
account_compare_op);

// So for every debitor, beginning with highest debt decreasing ...
for(c_id = 0; c_id < n_debitors; ++c_id) {
// Look for the most important creditor (at bottom of list, due to sorting order):
for(d_id = n_debitors;
d_id > c_id && accounts[c_id].total > 0; // if there's debt to be collected ...
--d_id)
{
subtotal = 0;
if(accounts[d_id].total != 0) { // if this debitor is unbalanced ...
subtotal = abs(accounts[d_id].total); // money owed always is negative
if(subtotal > accounts[c_id].total) { // total is greater than debt of c_id
subtotal = accounts[c_id].total; // so let's transfer what't available
print_transaction(accounts[d_id].id, accounts[c_id].id, subtotal);
accounts[d_id].total += subtotal;
accounts[c_id].total = 0;
}
else {
print_transaction(accounts[d_id].id, accounts[c_id].id, subtotal);
accounts[c_id].total -= subtotal;
accounts[d_id].total = 0;
}
}
}
}
}

int main(int argc, char * argv[])
{

int n_cases, n_names, n_transactions, i, max_amount, max_debitor;
n_cases = 0;
char name[100];
while(scanf("%d%d",&n_names, &n_transactions) && n_names > 0)
{
max_amount = 0;

for(i=0; i<n_names; ++i) // read participants
{
::std::string name_s;
::std::cin >> name_s;
create_debitor(name_s);
}
for(i=0; i<n_transactions; ++i) {
scanf("%s", &name);
::std::string from(name);
scanf("%s", &name);
::std::string to(name);
unsigned int amount;
scanf("%d", &amount);

add_debt(to, from, amount);
}
::std::cout << "Case #" << ++n_cases << ::std::endl;
balance_accounts();
::std::cout << ::std::endl;

// Reset for next network:
memset(accounts, 0, sizeof(accounts));
id_map.clear();
name_map.clear();
}
return 0;
}