4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <utility>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct Lottery
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<string> sortByOdds(vector<string> rules)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		vector< pair<long long, string> > lots;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<rules.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			stringstream sin(rules[i]);
4fd800b3a8 2011-02-23        kinaba: 			string name;
4fd800b3a8 2011-02-23        kinaba: 			int  ch, bl;
4fd800b3a8 2011-02-23        kinaba: 			char so, un;
4fd800b3a8 2011-02-23        kinaba: 			getline(sin, name, ':') >> ch >> bl >> so >> un;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			lots.push_back( make_pair(numChoice(ch,bl,so=='T',un=='T'), name) );
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		sort( lots.begin(), lots.end() );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<string> ans;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<lots.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 			ans.push_back( lots[i].second );
4fd800b3a8 2011-02-23        kinaba: 		return ans;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	long long numChoice(long long ch, long long bl, bool so, bool un)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// Note: so && !un
4fd800b3a8 2011-02-23        kinaba: 		//   3 out of 5  ===
4fd800b3a8 2011-02-23        kinaba: 		//      +|++++[5][5][5], +|+++[4]+[5][5], +|+++[4][4]+[5], ...
4fd800b3a8 2011-02-23        kinaba: 		//   === 3+5-1 C 3
4fd800b3a8 2011-02-23        kinaba: 		long long a = 1;
4fd800b3a8 2011-02-23        kinaba: 		if(so)
4fd800b3a8 2011-02-23        kinaba: 			for(long long i=1; i<=bl; ++i) a = a*(ch-i+(un?1:bl))/i;
4fd800b3a8 2011-02-23        kinaba: 		else
4fd800b3a8 2011-02-23        kinaba: 			while(bl--) a *= (un ? ch-- : ch);
4fd800b3a8 2011-02-23        kinaba: 		return a;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };