1ef2ecff66 2011-08-21        kinaba: #include <iostream>
1ef2ecff66 2011-08-21        kinaba: #include <sstream>
1ef2ecff66 2011-08-21        kinaba: #include <iomanip>
1ef2ecff66 2011-08-21        kinaba: #include <vector>
1ef2ecff66 2011-08-21        kinaba: #include <string>
1ef2ecff66 2011-08-21        kinaba: #include <map>
1ef2ecff66 2011-08-21        kinaba: #include <set>
1ef2ecff66 2011-08-21        kinaba: #include <algorithm>
1ef2ecff66 2011-08-21        kinaba: #include <numeric>
1ef2ecff66 2011-08-21        kinaba: #include <iterator>
1ef2ecff66 2011-08-21        kinaba: #include <functional>
1ef2ecff66 2011-08-21        kinaba: #include <complex>
1ef2ecff66 2011-08-21        kinaba: #include <queue>
1ef2ecff66 2011-08-21        kinaba: #include <stack>
1ef2ecff66 2011-08-21        kinaba: #include <cmath>
1ef2ecff66 2011-08-21        kinaba: #include <cassert>
1ef2ecff66 2011-08-21        kinaba: #include <cstring>
1ef2ecff66 2011-08-21        kinaba: using namespace std;
1ef2ecff66 2011-08-21        kinaba: typedef long long LL;
1ef2ecff66 2011-08-21        kinaba: typedef complex<double> CMP;
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: struct Event
1ef2ecff66 2011-08-21        kinaba: {
1ef2ecff66 2011-08-21        kinaba: 	int i, T, C, P;
1ef2ecff66 2011-08-21        kinaba: 	double P_total;
1ef2ecff66 2011-08-21        kinaba: 	bool has_next;
1ef2ecff66 2011-08-21        kinaba: 	Event(int i, int T, int C, int P) : i(i), T(T), C(C), P(P) {}
1ef2ecff66 2011-08-21        kinaba: 	bool operator<(const Event& rhs) const { return T < rhs.T; }
1ef2ecff66 2011-08-21        kinaba: };
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: class NewItemShop { public:
1ef2ecff66 2011-08-21        kinaba: 	double getMaximum(int swords, vector <string> customers)
1ef2ecff66 2011-08-21        kinaba: 	{
1ef2ecff66 2011-08-21        kinaba: 		vector<Event> ev;
1ef2ecff66 2011-08-21        kinaba: 		for(size_t i=0; i<customers.size(); ++i)
1ef2ecff66 2011-08-21        kinaba: 		{
1ef2ecff66 2011-08-21        kinaba: 			for(size_t k=0; k<customers[i].size(); ++k)
1ef2ecff66 2011-08-21        kinaba: 				if( customers[i][k] == ',' )
1ef2ecff66 2011-08-21        kinaba: 					customers[i][k] = ' ';
1ef2ecff66 2011-08-21        kinaba: 			stringstream ss(customers[i]);
1ef2ecff66 2011-08-21        kinaba: 			for(int T,C,P; ss>>T>>C>>P; )
1ef2ecff66 2011-08-21        kinaba: 				ev.push_back(Event((int)i,T,C,P));
1ef2ecff66 2011-08-21        kinaba: 		}
1ef2ecff66 2011-08-21        kinaba: 		sort(ev.begin(), ev.end());
1ef2ecff66 2011-08-21        kinaba: 		for(int i=0; i<ev.size(); ++i)
1ef2ecff66 2011-08-21        kinaba: 		{
1ef2ecff66 2011-08-21        kinaba: 			ev[i].P_total = 100;
1ef2ecff66 2011-08-21        kinaba: 			ev[i].has_next = false;
1ef2ecff66 2011-08-21        kinaba: 			for(int k=i+1; k<ev.size(); ++k)
1ef2ecff66 2011-08-21        kinaba: 				if( ev[k].i == ev[i].i )
1ef2ecff66 2011-08-21        kinaba: 					ev[i].has_next = true;
1ef2ecff66 2011-08-21        kinaba: 			for(int k=i-1; k>=0; --k)
1ef2ecff66 2011-08-21        kinaba: 				if( ev[k].i == ev[i].i )
1ef2ecff66 2011-08-21        kinaba: 					ev[i].P_total -= ev[k].P;
1ef2ecff66 2011-08-21        kinaba: 		}
1ef2ecff66 2011-08-21        kinaba: 		return rec(0, ev, swords, 0);
1ef2ecff66 2011-08-21        kinaba: 	}
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: 	map<int, double> memo;
1ef2ecff66 2011-08-21        kinaba: 	double rec(int i, const vector<Event>& ev, int swords, int mask)
1ef2ecff66 2011-08-21        kinaba: 	{
1ef2ecff66 2011-08-21        kinaba: 		if( i==ev.size() || swords==0 )
1ef2ecff66 2011-08-21        kinaba: 			return 0;
1ef2ecff66 2011-08-21        kinaba: 		int key = (mask*ev.size() + i) * 25 + swords;
1ef2ecff66 2011-08-21        kinaba: 		if( memo.count(key) )
1ef2ecff66 2011-08-21        kinaba: 			return memo[key];
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: 		const int ID = ev[i].i;
1ef2ecff66 2011-08-21        kinaba: 		const double C = ev[i].C;
1ef2ecff66 2011-08-21        kinaba: 		const double P = ev[i].P / ev[i].P_total;
1ef2ecff66 2011-08-21        kinaba: 		const int newmask = (ev[i].has_next ? mask|(1<<ID) : mask);
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: 		if( (1<<ID) & mask )
1ef2ecff66 2011-08-21        kinaba: 			return memo[key] = rec(i+1, ev, swords, mask);
1ef2ecff66 2011-08-21        kinaba: 		return memo[key] =
1ef2ecff66 2011-08-21        kinaba: 			      P * max(C+rec(i+1, ev, swords-1, newmask), rec(i+1, ev, swords, newmask))
1ef2ecff66 2011-08-21        kinaba: 			+ (1-P) * rec(i+1, ev, swords, mask);
1ef2ecff66 2011-08-21        kinaba: 	}
1ef2ecff66 2011-08-21        kinaba: };
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: // BEGIN CUT HERE
1ef2ecff66 2011-08-21        kinaba: #include <ctime>
1ef2ecff66 2011-08-21        kinaba: double start_time; string timer()
1ef2ecff66 2011-08-21        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
1ef2ecff66 2011-08-21        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
1ef2ecff66 2011-08-21        kinaba:  { os << "{ ";
1ef2ecff66 2011-08-21        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
1ef2ecff66 2011-08-21        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
1ef2ecff66 2011-08-21        kinaba: void verify_case(const double& Expected, const double& Received) {
1ef2ecff66 2011-08-21        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
1ef2ecff66 2011-08-21        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
1ef2ecff66 2011-08-21        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
1ef2ecff66 2011-08-21        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
1ef2ecff66 2011-08-21        kinaba: #define END	 verify_case(_, NewItemShop().getMaximum(swords, customers));}
1ef2ecff66 2011-08-21        kinaba: int main(){
1ef2ecff66 2011-08-21        kinaba: 
1ef2ecff66 2011-08-21        kinaba: CASE(0)
1ef2ecff66 2011-08-21        kinaba: 	int swords = 1;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = 19.0;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: CASE(1)
1ef2ecff66 2011-08-21        kinaba: 	int swords = 2;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = 21.8;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: CASE(2)
1ef2ecff66 2011-08-21        kinaba: 	int swords = 1;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = { "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,80" };
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = 90.0;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: CASE(3)
1ef2ecff66 2011-08-21        kinaba: 	int swords = 3;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = { "17,31,41 20,59,26 23,53,5", "19,89,79", "16,32,38 22,46,26", "18,43,38 21,32,7" };
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = 135.5121414;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: CASE(4)
1ef2ecff66 2011-08-21        kinaba: 	int swords = 5;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = { "1,1,10", "2,2,9", "3,3,8", "4,4,7", "5,5,6", "6,6,5", "7,7,4", "8,8,3", "9,9,2", "10,10,1" };
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = 2.1999744634845344;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: /*
1ef2ecff66 2011-08-21        kinaba: CASE(5)
1ef2ecff66 2011-08-21        kinaba: 	int swords = ;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = ;
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = ;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: CASE(6)
1ef2ecff66 2011-08-21        kinaba: 	int swords = ;
1ef2ecff66 2011-08-21        kinaba: 	string customers_[] = ;
1ef2ecff66 2011-08-21        kinaba: 	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
1ef2ecff66 2011-08-21        kinaba: 	double _ = ;
1ef2ecff66 2011-08-21        kinaba: END
1ef2ecff66 2011-08-21        kinaba: */
1ef2ecff66 2011-08-21        kinaba: }
1ef2ecff66 2011-08-21        kinaba: // END CUT HERE