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()-pm); 33 + } else { 34 + if(pm == lines[k].size()) 35 + best = min<int>(best, lines[i].size() - pm); 36 + else 37 + best = min<int>(best, 2 + lines[i].size() - pm); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 65 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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> roads) 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)], td); 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]!=INF) 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][mask|(1<<u)], td); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 114 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 115 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 116 +#define END verify_case(_, TravellingPurchasingMan().maxStores(N, interestingStores, roads));} 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_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); 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_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); 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_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); 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_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); 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_, interestingStores_+sizeof(interestingStores_)/sizeof(*interestingStores_)); 157 + string roads_[] = ; 158 + vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 159 + int _ = ; 160 +END 161 +*/ 162 +} 163 +// END CUT HERE