Overview
| SHA1 Hash: | 7cbc6cb50ea3dd8fc16e37f7db992c3098b02c3b |
|---|---|
| Date: | 2013-05-25 15:21:07 |
| User: | kinaba |
| Comment: | 579 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/579-U/1A.cpp version [2023aee3feb683a1]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<double> CMP; > 21 > 22 class UndoHistory { public: > 23 int minPresses(vector <string> lines) > 24 { > 25 int score = lines[0].size() + 1; > 26 for(int i=1; i<lines.size(); ++i) > 27 { > 28 int best = 0x7fffffff; > 29 for(int k=0; k<i; ++k) { > 30 int pm = prefix_match(lines[i], lines[k]); > 31 if(k<i-1) { > 32 best = min<int>(best, 2 + lines[i].size( > 33 } else { > 34 if(pm == lines[k].size()) > 35 best = min<int>(best, lines[i].s > 36 else > 37 best = min<int>(best, 2 + lines[ > 38 } > 39 } > 40 score += best+1; > 41 } > 42 return score; > 43 } > 44 > 45 int prefix_match(const string& a, const string& b) > 46 { > 47 int i = 0; > 48 while(i<a.size() && i<b.size() && a[i]==b[i]) > 49 ++i; > 50 return i; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const int& Expected, const int& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, UndoHistory().minPresses(lines));} > 68 int main(){ > 69 > 70 CASE(0) > 71 string lines_[] = {"tomorrow", "topcoder"}; > 72 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 73 int _ = 18; > 74 END > 75 CASE(1) > 76 string lines_[] = {"a","b"}; > 77 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 78 int _ = 6; > 79 END > 80 CASE(2) > 81 string lines_[] = {"a", "ab", "abac", "abacus" }; > 82 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 83 int _ = 10; > 84 END > 85 CASE(3) > 86 string lines_[] = {"pyramid", "sphinx", "sphere", "python", "serpent"}; > 87 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 88 int _ = 39; > 89 END > 90 CASE(4) > 91 string lines_[] = {"ba","a","a","b","ba"} > 92 ; > 93 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 94 int _ = 13; > 95 END > 96 /* > 97 CASE(5) > 98 string lines_[] = ; > 99 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 100 int _ = ; > 101 END > 102 CASE(6) > 103 string lines_[] = ; > 104 vector <string> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); > 105 int _ = ; > 106 END > 107 */ > 108 } > 109 // END CUT HERE
Added SRM/579-U/1B.cpp version [bab427bab8e79c47]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<double> CMP; > 21 > 22 int bitcnt(int x) > 23 { > 24 int c = 0; > 25 for(; x; x>>=1) > 26 c += x&1; > 27 return c; > 28 } > 29 > 30 class TravellingPurchasingMan { public: > 31 static const int INF = 0x3fffffff; > 32 struct Store { > 33 int open; > 34 int close; > 35 int shopping; > 36 }; > 37 > 38 int maxStores(int N, vector <string> interestingStores, vector <string> > 39 { > 40 vector< vector<int> > d(N, vector<int>(N, INF)); > 41 for(int i=0; i<N; ++i) > 42 d[i][i] = 0; > 43 for(int i=0; i<roads.size(); ++i) > 44 { > 45 stringstream sin(roads[i]); > 46 int a, b, len; > 47 sin >> a >> b >> len; > 48 d[a][b] = d[b][a] = len; > 49 } > 50 for(int k=0; k<N; ++k) > 51 for(int i=0; i<N; ++i) > 52 for(int j=0; j<N; ++j) > 53 d[i][j] = min(d[i][j], d[i][k]+d[k][j]); > 54 > 55 const int M = interestingStores.size(); > 56 vector<Store> s; > 57 for(int i=0; i<interestingStores.size(); ++i) > 58 { > 59 stringstream sin(interestingStores[i]); > 60 int op,cl,du; > 61 sin >> op >> cl >> du; > 62 Store st = {op,cl+1,du}; // [,) > 63 s.push_back(st); > 64 } > 65 > 66 vector< pair<int,int> > pop_mask; > 67 for(int mask=0; mask<(1<<M); ++mask) > 68 pop_mask.push_back(make_pair(bitcnt(mask), mask)); > 69 sort(pop_mask.begin(), pop_mask.end()); > 70 > 71 vector< vector<int> > tbl(M, vector<int>(1<<M, INF)); > 72 for(int u=0; u<M; ++u) { > 73 int t=0, v=N-1, mask=0; > 74 int ta = t + d[v][u]; > 75 int to = max(ta, s[u].open); > 76 if(to < s[u].close) { > 77 int td = to + s[u].shopping; > 78 tbl[u][mask|(1<<u)] = min(tbl[u][mask|(1<<u)], t > 79 } > 80 } > 81 > 82 int best = 0; > 83 for(int i=0; i<pop_mask.size(); ++i) { > 84 int mask = pop_mask[i].second; > 85 for(int v=0; v<M; ++v) if((mask&(1<<v)) && tbl[v][mask]! > 86 { > 87 best = pop_mask[i].first; > 88 int t = tbl[v][mask]; > 89 for(int u=0; u<M; ++u) if(!(mask&(1<<u))) { > 90 int ta = t + d[v][u]; > 91 int to = max(ta, s[u].open); > 92 if(to < s[u].close) { > 93 int td = to + s[u].shopping; > 94 tbl[u][mask|(1<<u)] = min(tbl[u] > 95 } > 96 } > 97 } > 98 } > 99 return best; > 100 } > 101 }; > 102 > 103 // BEGIN CUT HERE > 104 #include <ctime> > 105 double start_time; string timer() > 106 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 107 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 108 { os << "{ "; > 109 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 110 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 111 void verify_case(const int& Expected, const int& Received) { > 112 bool ok = (Expected == Received); > 113 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 114 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 115 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 116 #define END verify_case(_, TravellingPurchasingMan().maxStores(N, interesti > 117 int main(){ > 118 > 119 CASE(0) > 120 int N = 3; > 121 string interestingStores_[] = {"1 10 10" , "1 55 31", "10 50 100" }; > 122 vector <string> interestingStores(interestingStores_, interestingStore > 123 string roads_[] = {"1 2 10"}; > 124 vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 125 int _ = 1; > 126 END > 127 CASE(1) > 128 int N = 3; > 129 string interestingStores_[] = {"1 10 10" , "1 55 30", "10 50 100" }; > 130 vector <string> interestingStores(interestingStores_, interestingStore > 131 string roads_[] = {"1 2 10"}; > 132 vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 133 int _ = 2; > 134 END > 135 CASE(2) > 136 int N = 5; > 137 string interestingStores_[] = {"0 1000 17"}; > 138 vector <string> interestingStores(interestingStores_, interestingStore > 139 string roads_[] = {"2 3 400", "4 1 500", "4 3 300", "1 0 700", "0 2 400" > 140 vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 141 int _ = 0; > 142 END > 143 CASE(3) > 144 // if no wf is done. > 145 int N = 3; > 146 string interestingStores_[] = {"0 100 1"}; > 147 vector <string> interestingStores(interestingStores_, interestingStore > 148 string roads_[] = {"0 1 10", "1 2 10"}; > 149 vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 150 int _ = 1; > 151 END > 152 /* > 153 CASE(4) > 154 int N = ; > 155 string interestingStores_[] = ; > 156 vector <string> interestingStores(interestingStores_, interestingStore > 157 string roads_[] = ; > 158 vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); > 159 int _ = ; > 160 END > 161 */ > 162 } > 163 // END CUT HERE