Saturday, November 13, 2010

ACM - UVA 119 - greedy gift givers

Problem: 119 - greedy gift givers
Solution: C++
Hints: http://www.algorithmist.com/index.php/UVa_119


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>
using namespace std;

class Person
{
public:
       Person() : name(), numGiven(0), numRecieved(0) { }
       std::string name;
       int numGiven;
       int numRecieved;

       inline void give(int amount) { numGiven = amount; }
       inline void receive(int amount) { numRecieved += amount; }
       inline int assets() { return numRecieved - numGiven; }
};


int main(int argc, char** argv) 

{

        typedef vector<Person> Index;
        typedef map<std::string, Person*> Map;

        bool firstOutput = true;
        std::size_t n = 0;

        while (cin >> n)
        {
                // avoid printing leading whitespace
                if (!firstOutput) std::cout << std::endl;
                else firstOutput = false;

                Map peopleMap;
                Index people(n);

                // read names
                for (Index::iterator it = people.begin(); it != people.end(); ++it)
                {
                        std::cin >> it->name;
                        peopleMap[it->name] = &(*it);
                }
     
                std::string giverName, recieverName;
                std::size_t numRecievers = 0, numGiven = 0;

                // read in people each person gives to
                for (std::size_t i = 0; i < n; ++i)
                {

                        cin >> giverName >> numGiven >> numRecievers;
                        Person* giver = peopleMap[giverName];

                        for (std::size_t j = 0; j != numRecievers; ++j)
                        {
                                cin >> recieverName;
                                peopleMap[recieverName]->receive(numGiven / numRecievers);
                                giver->give(numGiven - (numGiven % numRecievers));
                        }
                }

                for (Index::iterator it = people.begin(); it != people.end(); ++it)
                {
                        cout << it->name << " " << it->assets() << endl;
                }

        }
}



    

No comments:

Post a Comment