Artifact 014f566256f8eca5f93f66f9de9c36bc4f164295

• File SRM/144/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
using namespace std;

struct Lottery
{
	vector<string> sortByOdds(vector<string> rules)
	{
		vector< pair<long long, string> > lots;
		for(int i=0; i<rules.size(); ++i)
		{
			stringstream sin(rules[i]);
			string name;
			int  ch, bl;
			char so, un;
			getline(sin, name, ':') >> ch >> bl >> so >> un;

			lots.push_back( make_pair(numChoice(ch,bl,so=='T',un=='T'), name) );
		}
		sort( lots.begin(), lots.end() );

		vector<string> ans;
		for(int i=0; i<lots.size(); ++i)
			ans.push_back( lots[i].second );
		return ans;
	}

	long long numChoice(long long ch, long long bl, bool so, bool un)
	{
		// Note: so && !un
		//   3 out of 5  ===
		//      +|++++[5][5][5], +|+++[4]+[5][5], +|+++[4][4]+[5], ...
		//   === 3+5-1 C 3
		long long a = 1;
		if(so)
			for(long long i=1; i<=bl; ++i) a = a*(ch-i+(un?1:bl))/i;
		else
			while(bl--) a *= (un ? ch-- : ch);
		return a;
	}
};