e.cpp

// Problem E: Helping Florida
// Author: Christopher Vo

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <sstream>
#include <algorithm>
using namespace std;
typedef vector<list<string> > db;

// compare entries by their votes
bool lessThan(const pair<string, int> & l, const pair<string, int> & r)
{
  return l.second < r.second;
}

int main()
{
  int num_c, num_b;
  string line;
  db::iterator bi;
  vector<string>::iterator si;
  map<string, int>::iterator mi;

  while (true) {
    // input number of candidates and ballots
    cin >> num_c >> num_b;
    cin.get();
    if (num_c == 0 && num_b == 0)
      break;

    // grab the ballots
    db ballots;
    ballots.resize(num_b);
    for (int i = 0; i < num_b; ++i) {
      string can;
      getline(cin, line);
      stringstream ll(line);
      while (ll >> can)
        ballots[i].push_back(can);
    }

    // process ballots
    while (true) {
      // tally
      map<string, int> tally;
      for (bi = ballots.begin(); bi != ballots.end(); ++bi)
        if (bi->size() > 0)
          tally[bi->front()]++;

      // one candidate? win.
      if (tally.size() == 1) {
        cout << tally.begin()->first << " won" << endl;
        break;
      }

      // >50% votes? win.
      bool win = false;
      for (mi = tally.begin(); mi != tally.end(); ++mi) {
        if (mi->second / (double) num_b > 0.5) {
          cout << mi->first << " won" << endl;
          win = true;
          break;
        }
      }
      if (win)
        break;

      // figure out who is to be eliminated
      int min = min_element(tally.begin(), tally.end(), lessThan)->second;
      vector<string> elim;
      for (mi = tally.begin(); mi != tally.end(); ++mi)
        if (mi->second == min)
          elim.push_back(mi->first);

      // if everyone is eliminated, it's a tie.
      if (elim.size() == tally.size()) {
        cout << "it is a tie between " << elim[0];
        for (si = elim.begin() + 1; si != elim.end(); ++si)
          cout << " and " << *si;
        cout << endl;
        break;
      }

      // finally, remove the eliminated candidates.
      for (si = elim.begin(); si != elim.end(); ++si)
        for (bi = ballots.begin(); bi != ballots.end(); ++bi)
          bi->remove(*si);
    }
  }
  return 0;
}