c5054cb313 2011-07-26 kinaba: #include <iostream> c5054cb313 2011-07-26 kinaba: #include <sstream> c5054cb313 2011-07-26 kinaba: #include <iomanip> c5054cb313 2011-07-26 kinaba: #include <vector> c5054cb313 2011-07-26 kinaba: #include <string> c5054cb313 2011-07-26 kinaba: #include <map> c5054cb313 2011-07-26 kinaba: #include <set> c5054cb313 2011-07-26 kinaba: #include <algorithm> c5054cb313 2011-07-26 kinaba: #include <numeric> c5054cb313 2011-07-26 kinaba: #include <iterator> c5054cb313 2011-07-26 kinaba: #include <functional> c5054cb313 2011-07-26 kinaba: #include <complex> c5054cb313 2011-07-26 kinaba: #include <queue> c5054cb313 2011-07-26 kinaba: #include <stack> c5054cb313 2011-07-26 kinaba: #include <cmath> c5054cb313 2011-07-26 kinaba: #include <cassert> c5054cb313 2011-07-26 kinaba: #include <cstring> c5054cb313 2011-07-26 kinaba: using namespace std; c5054cb313 2011-07-26 kinaba: typedef long long LL; c5054cb313 2011-07-26 kinaba: typedef complex<double> CMP; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: class MysteriousRestaurant { public: c5054cb313 2011-07-26 kinaba: int maxDays(vector <string> prices, int budget) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: for(int D=prices.size(); D>=0; --D) c5054cb313 2011-07-26 kinaba: if( ok(D, prices, budget) ) c5054cb313 2011-07-26 kinaba: return D; c5054cb313 2011-07-26 kinaba: return 0; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: bool ok(int D, const vector<string>& prices, int budget) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: int M = prices[0].size(); c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: vector< vector<int> > p(7, vector<int>(M)); c5054cb313 2011-07-26 kinaba: for(int i=0; i<D; ++i) c5054cb313 2011-07-26 kinaba: for(int m=0; m<M; ++m) c5054cb313 2011-07-26 kinaba: p[i%7][m] += toPrice(prices[i][m]); c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: int cost = 0; c5054cb313 2011-07-26 kinaba: for(int i=0; i<7; ++i) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: int least = 0x7fffffff; c5054cb313 2011-07-26 kinaba: for(int m=0; m<M; ++m) c5054cb313 2011-07-26 kinaba: least = min(least, p[i][m]); c5054cb313 2011-07-26 kinaba: cost += least; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: return cost <= budget; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: int toPrice(char c) c5054cb313 2011-07-26 kinaba: { c5054cb313 2011-07-26 kinaba: if(c<='9') c5054cb313 2011-07-26 kinaba: return c-'0'; c5054cb313 2011-07-26 kinaba: if(c<='Z') c5054cb313 2011-07-26 kinaba: return c-'A'+10; c5054cb313 2011-07-26 kinaba: return c-'a'+36; c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: }; c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: // BEGIN CUT HERE c5054cb313 2011-07-26 kinaba: #include <ctime> c5054cb313 2011-07-26 kinaba: double start_time; string timer() c5054cb313 2011-07-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c5054cb313 2011-07-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c5054cb313 2011-07-26 kinaba: { os << "{ "; c5054cb313 2011-07-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c5054cb313 2011-07-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c5054cb313 2011-07-26 kinaba: void verify_case(const int& Expected, const int& Received) { c5054cb313 2011-07-26 kinaba: bool ok = (Expected == Received); c5054cb313 2011-07-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c5054cb313 2011-07-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c5054cb313 2011-07-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c5054cb313 2011-07-26 kinaba: #define END verify_case(_, MysteriousRestaurant().maxDays(prices, budget));} c5054cb313 2011-07-26 kinaba: int main(){ c5054cb313 2011-07-26 kinaba: c5054cb313 2011-07-26 kinaba: CASE(0) c5054cb313 2011-07-26 kinaba: string prices_[] = {"26", "14", "72", "39", "32", "85", "06"}; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = 13; c5054cb313 2011-07-26 kinaba: int _ = 5; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(1) c5054cb313 2011-07-26 kinaba: string prices_[] = {"26", "14", "72", "39", "32", "85", "06", "91"}; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = 20; c5054cb313 2011-07-26 kinaba: int _ = 8; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(2) c5054cb313 2011-07-26 kinaba: string prices_[] = {"SRM", "512"}; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = 4; c5054cb313 2011-07-26 kinaba: int _ = 0; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(3) c5054cb313 2011-07-26 kinaba: string prices_[] = {"Dear", "Code", "rsHa", "veFu", "nInT", "heCh", "alle", "ngeP", "hase", "andb", "ecar", "eful"}; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = 256; c5054cb313 2011-07-26 kinaba: int _ = 10; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: /* c5054cb313 2011-07-26 kinaba: CASE(4) c5054cb313 2011-07-26 kinaba: string prices_[] = ; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = ; c5054cb313 2011-07-26 kinaba: int _ = ; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: CASE(5) c5054cb313 2011-07-26 kinaba: string prices_[] = ; c5054cb313 2011-07-26 kinaba: vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_)); c5054cb313 2011-07-26 kinaba: int budget = ; c5054cb313 2011-07-26 kinaba: int _ = ; c5054cb313 2011-07-26 kinaba: END c5054cb313 2011-07-26 kinaba: */ c5054cb313 2011-07-26 kinaba: } c5054cb313 2011-07-26 kinaba: // END CUT HERE