ADDED SRM/579-U/1A.cpp Index: SRM/579-U/1A.cpp ================================================================== --- SRM/579-U/1A.cpp +++ SRM/579-U/1A.cpp @@ -0,0 +1,109 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex<double> CMP; + +class UndoHistory { public: + int minPresses(vector <string> lines) + { + int score = lines[0].size() + 1; + for(int i=1; i<lines.size(); ++i) + { + int best = 0x7fffffff; + for(int k=0; k<i; ++k) { + int pm = prefix_match(lines[i], lines[k]); + if(k<i-1) { + best = min<int>(best, 2 + lines[i].size()-pm); + } else { + if(pm == lines[k].size()) + best = min<int>(best, lines[i].size() - pm); + else + best = min<int>(best, 2 + lines[i].size() - pm); + } + } + score += best+1; + } + return score; + } + + int prefix_match(const string& a, const string& b) + { + int i = 0; + while(i<a.size() && i<b.size() && a[i]==b[i]) + ++i; + return i; + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, UndoHistory().minPresses(lines));} +int main(){ + +CASE(0) + string lines_[] = {"tomorrow", "topcoder"}; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 18; +END +CASE(1) + string lines_[] = {"a","b"}; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 6; +END +CASE(2) + string lines_[] = {"a", "ab", "abac", "abacus" }; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 10; +END +CASE(3) + string lines_[] = {"pyramid", "sphinx", "sphere", "python", "serpent"}; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 39; +END +CASE(4) + string lines_[] = {"ba","a","a","b","ba"} +; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = 13; +END +/* +CASE(5) + string lines_[] = ; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = ; +END +CASE(6) + string lines_[] = ; + vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); + int _ = ; +END + */ +} +// END CUT HERE ADDED SRM/579-U/1B.cpp Index: SRM/579-U/1B.cpp ================================================================== --- SRM/579-U/1B.cpp +++ SRM/579-U/1B.cpp @@ -0,0 +1,163 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex<double> CMP; + +int bitcnt(int x) +{ + int c = 0; + for(; x; x>>=1) + c += x&1; + return c; +} + +class TravellingPurchasingMan { public: + static const int INF = 0x3fffffff; + struct Store { + int open; + int close; + int shopping; + }; + + int maxStores(int N, vector <string> interestingStores, vector <string> roads) + { + vector< vector<int> > d(N, vector<int>(N, INF)); + for(int i=0; i<N; ++i) + d[i][i] = 0; + for(int i=0; i<roads.size(); ++i) + { + stringstream sin(roads[i]); + int a, b, len; + sin >> a >> b >> len; + d[a][b] = d[b][a] = len; + } + for(int k=0; k<N; ++k) + for(int i=0; i<N; ++i) + for(int j=0; j<N; ++j) + d[i][j] = min(d[i][j], d[i][k]+d[k][j]); + + const int M = interestingStores.size(); + vector<Store> s; + for(int i=0; i<interestingStores.size(); ++i) + { + stringstream sin(interestingStores[i]); + int op,cl,du; + sin >> op >> cl >> du; + Store st = {op,cl+1,du}; // [,) + s.push_back(st); + } + + vector< pair<int,int> > pop_mask; + for(int mask=0; mask<(1<<M); ++mask) + pop_mask.push_back(make_pair(bitcnt(mask), mask)); + sort(pop_mask.begin(), pop_mask.end()); + + vector< vector<int> > tbl(M, vector<int>(1<<M, INF)); + for(int u=0; u<M; ++u) { + int t=0, v=N-1, mask=0; + int ta = t + d[v][u]; + int to = max(ta, s[u].open); + if(to < s[u].close) { + int td = to + s[u].shopping; + tbl[u][mask|(1<<u)] = min(tbl[u][mask|(1<<u)], td); + } + } + + int best = 0; + for(int i=0; i<pop_mask.size(); ++i) { + int mask = pop_mask[i].second; + for(int v=0; v<M; ++v) if((mask&(1<<v)) && tbl[v][mask]!=INF) + { + best = pop_mask[i].first; + int t = tbl[v][mask]; + for(int u=0; u<M; ++u) if(!(mask&(1<<u))) { + int ta = t + d[v][u]; + int to = max(ta, s[u].open); + if(to < s[u].close) { + int td = to + s[u].shopping; + tbl[u][mask|(1<<u)] = min(tbl[u][mask|(1<<u)], td); + } + } + } + } + return best; + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, TravellingPurchasingMan().maxStores(N, interestingStores, roads));} +int main(){ + +CASE(0) + int N = 3; + string interestingStores_[] = {"1 10 10" , "1 55 31", "10 50 100" }; + vector <string> interestingStores(interestingStores_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); + string roads_[] = {"1 2 10"}; + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); + int _ = 1; +END +CASE(1) + int N = 3; + string interestingStores_[] = {"1 10 10" , "1 55 30", "10 50 100" }; + vector <string> interestingStores(interestingStores_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); + string roads_[] = {"1 2 10"}; + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); + int _ = 2; +END +CASE(2) + int N = 5; + string interestingStores_[] = {"0 1000 17"}; + vector <string> interestingStores(interestingStores_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); + string roads_[] = {"2 3 400", "4 1 500", "4 3 300", "1 0 700", "0 2 400"}; + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); + int _ = 0; +END +CASE(3) +// if no wf is done. + int N = 3; + string interestingStores_[] = {"0 100 1"}; + vector <string> interestingStores(interestingStores_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); + string roads_[] = {"0 1 10", "1 2 10"}; + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); + int _ = 1; +END +/* +CASE(4) + int N = ; + string interestingStores_[] = ; + vector <string> interestingStores(interestingStores_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); + string roads_[] = ; + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); + int _ = ; +END +*/ +} +// END CUT HERE