#include <algorithm>
#include <iterator>
#include <iostream>	// For I/O
#include <vector>	// For vectors (arrays)
#include <limits>	// For epsilon
#include <list>
#include <set>		// For sets (solid coalitions, and duplicate removal)

#include <math.h>
#include <assert.h>

using namespace std;

// SET WEBSTER
//
// The general idea of Set Webster is: Each solid coalition is entitled to as 
// many seats as the minimum of round(voters_supporting / divisor) and the size
// of the coalition, where voters_supporting is the number of voters supporting
// that coalition (ranking coalition members ahead of all others).
//
// Doing so produces a set of constraints, of the form "the council should have
// this many from this set". Going down the list of solid coalitions in order 
// from the coalition of greatest support to that of least support, we admit 
// the constraint unless it would conflict with some earlier constraint, in 
// which case we note a contradiction of magnitude equal to the number of 
// voters supporting the coalition.
//
// The divisor that provides the least number of contradictions wins.
//
// In the case that every voter ranks his preferred party first, and all
// candidates of that party, equal ranked ahead of all the other parties equal-
// ranked last, the system easily reduces to ordinary Webster.
//
// If the nice properties of Webster holds, we can expect the method to be
// house monotone (provides a proportional ordering), population-pair monotone
// (passes mono-raise), and near the quota (you can't make two coalitions better
// off by switching a seat from one to the other). It doesn't actually meet
// quota.
//
// In the single-winner case, Set Webster reduces to DAC/DSC/DHSC, which isn't
// that good. If one considers DAC better than IRV, then this at least counts
// in Set Webster's favor; and even if not, the two monotonicity properties
// put Set Webster ahead of STV.

// There are two ways to calculate the winners. The first is to simply start
// with a set of all councils of the desired size and then check for
// contradictions, but this suffers combinatorial explosion. The second is to
// make use of the house monotonicity property, and recursively only consider
// sets including the winners so far.

// We'll implement the former. By using a tree to represent the sets implicitly,
// as well as pruning those sets that can never gain a single seat, it should 
// be possible to implement the latter in worst case polytime, but that has not 
// been done here. (It also requires better contradiction checker, so that it
// doesn't have to construct all the sets.)

// ---

// Get the least and greatest divisor that, when used to divide the number of
// voters, then rounded off, gives the number of seats. Any divisor we want to
// use must be within that range. This is a closed interval, and so are always
// checked.
pair<double, double> get_divisor_bounds(int num_voters, int council_size) {

	// The least number we can have without going below the number of seats
	// is council_size - 0.5. The greatest number we can have without going
	// above the number of seats is council_size + 0.5 - eps, for some very
	// low value of eps. We find out eps by multiplying by 1 + the machine
	// epsilon.
	
	pair<double, double> bounds;

	// Remove the epsilon and use 1e-2 instead if you want to see that
	// the numbers are different. Because of the small nature of epsilon,
	// it doesn't show up in debug statements.
	bounds.first = num_voters / (council_size + 0.5);
	bounds.first *= 1 + numeric_limits<double>::epsilon();
	bounds.second= num_voters / (council_size - 0.5);

	//cout << "NV: " << num_voters << endl;
	//cout << "GDB" << round(num_voters/bounds.first) << "\t" << num_voters / (council_size + 0.5) << endl;

	return(bounds);
}

// In order to figure out which divisors we have to check, we have to find the
// so-called tipping or inflection points. A tipping point at divisor d exists
// for a coalition of support x if round(x/d) = p, and this is the greatest
// value of d for which that is true. Tipping points provide the positions
// where the constraints of a solid coalition change, therefore, we must check
// each of them in order to be sure to check all possible divisors that "make a
// difference".
//
// In order not to clutter the list of tipping points unduly, we don't add
// points that would fall outside of the divisor range given by the number of
// seats, nor do we add those that gives the coalition more seats than there 
// are available seats in total, because neither are relevant to the comparison
// in Set Webster.

// By a bit of a hack, the function below also checks lower_divisor and
// upper_divisor themselves. If both divisors round to the same result, then
// there are no relevant tipping points, for instance. That is done implicitly
// by starting at the rounded value the upper divisor produces and then
// advancing to the rounded value the lower divisor produces.

// Note that the function is naive, and thus may add more points than are
// required. Consider the following example:
//
// A: 00000111111222222
// B: 00011111122222222
//     x     y     z
//
// By adding only points x, y, and z, we could get with checking only three
// divisors. However, since the find_all_between function for A doesn't know
// about B (and vice versa), it'll add extraneous points instead of homing
// directly onto x, y, and z.

// There's probably a clever algorithm to do this (involving determining lower
// and upper bounds for all), but for the sake of clarity, we won't have it 
// here.

vector<double> find_all_between(double support, double lower_divisor,
		double upper_divisor, int cardinality) {

	// Here we make use of the observation that if x/d is a tipping point,
	// then so is the d' so that x'/d = 1 + x/d.
	
	vector<double> points;

	// By using greatest_number and least_number, we add the edge divisors 
	// if there's any point in doing so, and also terminate when we exceed 
	// the cardinality of the set.

	// This uses a trick. If the divisor would exceed cardinality,
	// it uses lower divisor. This does make it exceed cardinality, but
	// the seats_deserved min function inside Set Webster itself corrects
	// it back. "A difference that makes no difference is no difference".
	int greatest_number = min((int)round(support/lower_divisor),
			cardinality);
	int least_number = round(support/upper_divisor);

	for (int counter = least_number; counter <= greatest_number; ++counter){

		// General case: least we can have without rounding to a
		// different integer.
		double candidate = support / (counter - 0.5);

		// Special cases for first and last.
		if (counter == least_number || candidate < 0)
			candidate = upper_divisor;
		if (counter == greatest_number)
			candidate = lower_divisor;

		points.push_back(candidate);
	}

	return(points);
}

// Simple structure for a solid coalition: a set of all candidates in the
// coalition, as well as the number of voters supporting it.

struct solid_coalition {
	set<int> candidates;
	double support;
};

// This function returns an array of all the unique tipping points when given
// an array of solid coalitions, as well as the interval defining valid
// divisors.
vector<double> get_tipping_points(const vector<solid_coalition> & sets,
		double lower_divisor, double upper_divisor) {

	// For all solid coalitions, add all their divisors to a set (so that
	// duplicates are removed). Then add the upper limit - the divisors
	// list should already contain the lower limit.
	
	set<double> tipping_points;

	for (int counter = 0; counter < sets.size(); ++counter) {
		vector<double> this_coalition_points = find_all_between(
				sets[counter].support, lower_divisor,
				upper_divisor, sets[counter].candidates.size());

		copy(this_coalition_points.begin(), this_coalition_points.end(),
				inserter(tipping_points, tipping_points.
					begin()));
	}

	// Add the edge divisors
	// But note, adding lower_divisor makes num_seats = 2 go wrong (two
	// that check the same outcome). Not doing it makes num_seats = 1 go
	// wrong (doesn't check = 100, lower criterion).
	if (tipping_points.empty()) 
		tipping_points.insert(lower_divisor);

	// Dump the set into the vector to return.
	// XXX? Use sets instead for clarity?
	vector<double> points_array;

	copy(tipping_points.begin(), tipping_points.end(), inserter(
				points_array, points_array.begin()));

	return(points_array);
}

//// 

// This function produces all unique sets that can be constructed by picking
// how_many members from the "from" set. It's used for the exhaustive search
// approach. "scratch" is a scratch list used because set automatically sorts.
void get_combinations(const set<int> & from, list<int> & scratch,
		list<set<int> > & output, int how_many, 
		set<int>::const_iterator curpos) {

	if (how_many == 0) { // Ready to copy? If so, do it
		set<int> this_set;
		copy(scratch.begin(), scratch.end(), inserter(this_set,
					this_set.begin()));
		output.push_back(this_set);
	} else {
		// Pick an unpicked candidate, then recurse
		while (curpos != from.end()) {
			scratch.push_back(*curpos);
			get_combinations(from, scratch, output, 
					how_many-1,++curpos);
			scratch.pop_back();
		}
	}
}

// This function appends a particular set to all sets provided to it. It's used
// in the recursive definition that makes use of house monotonicity.
void append(const set<int> & common, list<set<int> > & append_to) {

	for (list<set<int> >::iterator pos = append_to.begin(); pos !=
			append_to.end(); ++pos)
		copy(common.begin(), common.end(), inserter(*pos,
					pos->begin()));
}

// This function checks which sets, among those provided to it, are consistent
// with the constraint also provided to it. It returns those sets that are,
// indeed, consistent.
// For each input, we make an intersection of that input and the coalition set.
// If this intersection has cardinality less than the number of desired members
// from the coalition, then there's no way to fulfill the criterion. Otherwise,
// if the cardinality is greater or equal to the constraint, the set fulfills
// the constraint, and we can pass it on.
//
// We can use this function to gradually exclude sets that contradict. If all
// sets are excluded, there's a contradiction (and so we skip).
set<set<int> > reduce_candidates(const set<set<int> > & input, const
		solid_coalition & reduce_by, int constraint) {

	// If constraint > set of solid coalition, oops! That shouldn't
	// happen.
	assert (constraint <= reduce_by.candidates.size());

	set<set<int> > output;

	for (set<set<int> > ::const_iterator pos = input.begin(); pos !=
			input.end(); ++pos) {
		set<int> intersect;

		// Get the intersection set, so we can count if it has >=
		// the number of members given by the constraint.
		set_intersection(pos->begin(), pos->end(),
				reduce_by.candidates.begin(),
				reduce_by.candidates.end(), inserter(
					intersect, intersect.begin()));

		if (intersect.size() == constraint)
			output.insert(*pos);
	}

	return(output);
}

// This function returns the winning council and the penalty (number of voters
// we contradicted) for that council, given a divisor and the set of solid
// coalitions, and optionally a smaller council for the recursive 
// implementation.

// The coalitions must be in sorted order, coalition supported by most voters
// first, and so that the coalition of all candidates is the first.

struct check_info {
	double penalty;
	set<int> winners;
	bool used_tiebreak;
};

check_info check_option(const vector<solid_coalition> & coalitions,
		double divisor, int council_size, bool use_previous_result,
		const set<int> & previous_council, bool debug) {

	// This is the set of all possible sets.
	set<set<int> > retained;

	// If use_previous_result is false, then generate the set of all
	// possible councils. If it's true, generate the set of the old council
	// plus each candidate, which makes for all possible councils
	// consistent with house monotonicity.
	
	list<set<int> > possible_additions;

	if (use_previous_result) {
		list<int> scratch;

		assert(previous_council.size() == council_size - 1);

		get_combinations(coalitions[0].candidates, scratch, 
				possible_additions, 1, 
				coalitions[0].candidates.begin());

		append(previous_council, possible_additions);
	} else {
		list<int> scratch;

		get_combinations(coalitions[0].candidates, scratch,
				possible_additions, council_size,
				coalitions[0].candidates.begin());
	}

	copy(possible_additions.begin(), possible_additions.end(),
			inserter(retained, retained.begin()));

	double penalty = 0;

	if (debug)
		cout << "Divisor: " << divisor << "\t";

	for (int counter = 0; counter < coalitions.size(); ++counter) {
		// Each coalition deserves the minimum of the number of seats
		// given by the divisor and voter support, and the number of
		// candidates in the coalition.
		int seats_deserved = min(coalitions[counter].candidates.size(),
				(size_t)round(coalitions[counter].support /
					divisor));

		if (debug)
			cout << seats_deserved << " ";

		set<set<int> > next_iter = reduce_candidates(retained,
				coalitions[counter], seats_deserved);

		// If it's a contradiction, add to the penalty. Otherwise, set
		// retained to what remains after this round's narrowing.
		if (next_iter.empty())
			penalty += coalitions[counter].support;
		else	retained = next_iter;
	}

	if (debug)
		cout << endl;

	// We handle ties (more than one set left in the end) by picking one
	// at random. Better approaches may exist (Random Voter Hierarchy as
	// tiebreak); also, this may cause problems with house monotonicity.
	
	if (debug) {
		cout << "w-sets: " << retained.size() << " penalty: " 
			<< penalty << "\t";
		copy(retained.begin()->begin(), retained.begin()->end(),
				ostream_iterator<int>(cout, " "));
		cout << endl;
	}

	int pick = random() % retained.size();
	check_info outcome;
	for (set<set<int> >::const_iterator pos = retained.begin(); pos !=
			retained.end() && pick >= 0; ++pos)
		if (pick-- == 0)
			outcome.winners = *pos;

	outcome.used_tiebreak = (retained.size() > 1);
	outcome.penalty = penalty;

	return(outcome);
}

set<int> set_webster(const vector<solid_coalition> & coalitions, 
		int council_size, bool use_previous_council, const set<int> &
		previous_council, bool debug) {

	// Find the range of divisors...
	
	pair<double, double> bounds = get_divisor_bounds(coalitions[0].support,
			council_size);

	// Get the tipping points
	
	vector<double> tipping = get_tipping_points(coalitions, bounds.first,
			bounds.second);

	if (debug) {
		copy(tipping.begin(), tipping.end(), ostream_iterator<double>(
					cout, "\t"));
		cout << endl;
	}

	check_info best;
	best.penalty = INFINITY; // so we're assured that it'll be overwritten.

	// Then get the best result by trying all tipping points.
	for (int counter = 0; counter < tipping.size(); ++counter) {
		check_info this_solution = check_option(coalitions,
				tipping[counter], council_size, 
				use_previous_council, previous_council,
				debug);

		// If it's better outright, adopt it
		if (this_solution.penalty < best.penalty)
			best = this_solution;
		else
			// If it has equal penalty but doesn't use a tiebreak,
			// adopt it.
			if (this_solution.penalty == best.penalty &&
					!this_solution.used_tiebreak)
				best = this_solution;
	}

	// In order to make full use of house monotonicity, it should return
	// a set of sets instead of just a set, when the tiebreaker has been
	// used. That's not done here.
	return(best.winners);
}

// And finally, the interfaces!

set<int> naive_set_webster(const vector<solid_coalition> & coalitions,
		int council_size, bool debug) {

	return(set_webster(coalitions, council_size, false, set<int>(), debug));
}

set<int> sophisticated_set_webster(const vector<solid_coalition> & coalitions,
		int council_size, bool debug) {

	set<int> output = naive_set_webster(coalitions, 1, debug);

	for (int counter = 2; counter <= council_size; ++counter)
		output = set_webster(coalitions, counter, true, output, debug);

	return(output);
}

// Auxiliary functions. These aren't needed for Set Webster, but used to make
// it easier to specify solid coalitions for it to work on.

solid_coalition construct_sc(string memberset, double support) {
        solid_coalition output;

        for (int counter = 0; counter < memberset.size(); ++counter)
                output.candidates.insert(memberset[counter]-'A');

        output.support = support;
        return(output);
}

string show_membership(const set<int> & x) {
        string out;

        for (set<int>::const_iterator p = x.begin(); p != x.end(); ++p)
                out += 'A' + *p;

        return(out);
}

string show_membership(const solid_coalition & x) {
        return(show_membership(x.candidates));
}

main() {

	int num_seats = 4;
	bool debug = true;

	vector<solid_coalition> scs;
	// Enter your solid coalitions here, in sorted order. Break sorting
	// ties by the cardinality of the coalition's set, greater first.
	/*scs.push_back(construct_sc("ABCDEF", 150));
	scs.push_back(construct_sc("ABCDE", 150));
	scs.push_back(construct_sc("ABCD", 150));
	scs.push_back(construct_sc("ABC", 100));
	scs.push_back(construct_sc("AB", 100));
	scs.push_back(construct_sc("A", 100));
	scs.push_back(construct_sc("DEF", 50));
	scs.push_back(construct_sc("DE", 50));
	scs.push_back(construct_sc("D", 50));*/

	// PSC-CLE example, where no zero-contradiction council exists
	scs.push_back(construct_sc("ABCD", 100));
	scs.push_back(construct_sc("ABD", 68));
	scs.push_back(construct_sc("AD", 34));
	scs.push_back(construct_sc("BD", 33));
	scs.push_back(construct_sc("A", 33));
	scs.push_back(construct_sc("B", 33));
	scs.push_back(construct_sc("ACD", 32));
	scs.push_back(construct_sc("CD", 32));
	scs.push_back(construct_sc("C", 32));
	scs.push_back(construct_sc("D", 2));

	srandom(3);
	int counter;

	for (counter = 1; counter <= num_seats; ++counter)
		cout << "Sophisticated: " << show_membership(sophisticated_set_webster(scs, counter, false)) << endl;

	// Show house monotonicity.
	for (int counter = 1; counter <= num_seats; ++counter)
		cout << "Naive: " << show_membership(naive_set_webster(scs, 
					counter, debug)) << endl;
}