Overview
| SHA1 Hash: | 4e41a11c3852de0a0d6bcd97ea14a1c919b8b275 |
|---|---|
| Date: | 2011-06-18 15:53:46 |
| User: | kinaba |
| Comment: | 509 |
| 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/509-U/1A.cpp version [712b40dbdb712dc9]
> 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 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class LuckyRemainder { public: > 23 int getLuckyRemainder(string X) > 24 { > 25 int sum = 0; > 26 int N = X.size()-1; > 27 for(int i=0; i<X.size(); ++i) > 28 { > 29 int v = X[i]-'0'; > 30 for(int i=0; i<N; ++i) > 31 v = (v*2)%9; > 32 sum = (sum+v)%9; > 33 } > 34 return sum; > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const int& Expected, const int& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, LuckyRemainder().getLuckyRemainder(X));} > 52 int main(){ > 53 > 54 CASE(0) > 55 string X = "123"; > 56 int _ = 6; > 57 END > 58 CASE(1) > 59 string X = "24816"; > 60 int _ = 3; > 61 END > 62 CASE(2) > 63 string X = "8"; > 64 int _ = 8; > 65 END > 66 CASE(3) > 67 string X = "11235813213455"; > 68 int _ = 7; > 69 END > 70 CASE(4) > 71 string X = "1"; > 72 int _ = 1; > 73 END > 74 CASE(4) > 75 string X = "4"; > 76 int _ = 4; > 77 END > 78 CASE(4) > 79 string X = "9"; > 80 int _ = 0; > 81 END > 82 /* > 83 CASE(5) > 84 string X = ; > 85 int _ = ; > 86 END > 87 */ > 88 } > 89 // END CUT HERE
Added SRM/509-U/1B.cpp version [665b46c2c4b5b562]
> 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 #include <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class PalindromizationDiv1 { public: > 23 static const int INF = 0x3fffffff; > 24 static const int NOLETTER = 26; > 25 > 26 int getMinimumCost(string word, vector <string> operations) > 27 { > 28 // Cost for changing a character to another > 29 int cost[27][27]; > 30 for(int a=0; a<27; ++a) > 31 for(int b=0; b<27; ++b) > 32 cost[a][b] = (a==b ? 0 : INF); > 33 > 34 for(size_t i=0; i<operations.size(); ++i) > 35 { > 36 stringstream cin(operations[i]); > 37 string cmd; cin >> cmd; > 38 > 39 char a, b; int c; > 40 if( cmd == "add" ) { cin >> a >> c; cost[NOLETTER > 41 if( cmd == "erase" ) { cin >> a >> c; cost[ a - 'a' > 42 if( cmd == "change" ){ cin >> a >> b >> c; cost[ a - 'a' > 43 } > 44 > 45 // Warshall-Floyd > 46 for(int k=0; k<27; ++k) > 47 for(int i=0; i<27; ++i) > 48 for(int j=0; j<27; ++j) > 49 cost[i][j] = min(cost[i][j], cost[i][k]+ > 50 > 51 // Cost for matching two letters > 52 int match_cost[27][27]; > 53 for(int i=0; i<27; ++i) > 54 for(int j=0; j<27; ++j) > 55 { > 56 match_cost[i][j] = INF; > 57 for(int k=0; k<27; ++k) > 58 match_cost[i][j] = min(match_cost[i][j], > 59 } > 60 > 61 // Solve > 62 memo.clear(); > 63 int r = rec(match_cost, word, 0, word.size()-1); > 64 return (r>=INF ? -1 : r); > 65 } > 66 > 67 map<pair<int,int>,int> memo; > 68 int rec(const int mc[27][27], const string& w, int s, int e) > 69 { > 70 // Base case > 71 if( s >= e ) > 72 return 0; > 73 > 74 // Memoizaion > 75 const pair<int,int> key(s, e); > 76 if( memo.count(key) ) > 77 return memo[key]; > 78 > 79 // take best > 80 int result = INF; > 81 result = min(result, rec(mc, w, s+1, e-1)+mc[w[s]-'a'][w[e]-'a'] > 82 result = min(result, rec(mc, w, s, e-1)+mc[NOLETTER][w[e]-'a'] > 83 result = min(result, rec(mc, w, s+1, e )+mc[w[s]-'a'][NOLETTER] > 84 return memo[key] = result; > 85 } > 86 }; > 87 > 88 // BEGIN CUT HERE > 89 #include <ctime> > 90 double start_time; string timer() > 91 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 92 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 93 { os << "{ "; > 94 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 95 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 96 void verify_case(const int& Expected, const int& Received) { > 97 bool ok = (Expected == Received); > 98 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 99 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 100 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 101 #define END verify_case(_, PalindromizationDiv1().getMinimumCost(word, oper > 102 int main(){ > 103 > 104 CASE(0) > 105 string word = "racecar"; > 106 vector <string> operations; > 107 int _ = 0; > 108 END > 109 CASE(1) > 110 string word = "topcoder"; > 111 string operations_[] = {"erase t 1", "erase o 1", "erase p 1", "erase c > 112 vector <string> operations(operations_, operations_+sizeof(operations_ > 113 int _ = 5; > 114 END > 115 CASE(2) > 116 string word = "topcoder"; > 117 string operations_[] = {"erase t 10", "erase o 1", "erase p 1", "erase c > 118 vector <string> operations(operations_, operations_+sizeof(operations_ > 119 int _ = 7; > 120 END > 121 CASE(3) > 122 string word = "caaaaaab"; > 123 string operations_[] = {"change b a 100000", "change c a 100000", "chang > 124 vector <string> operations(operations_, operations_+sizeof(operations_ > 125 int _ = 199999; > 126 END > 127 CASE(4) > 128 string word = "moon"; > 129 string operations_[] = {"erase o 5", "add u 7", "change d p 3", "change > 130 vector <string> operations(operations_, operations_+sizeof(operations_ > 131 int _ = -1; > 132 END > 133 CASE(5) > 134 string word = "a"; > 135 vector <string> operations; > 136 int _ = 0; > 137 END > 138 CASE(6) // killer! > 139 string word = "az"; > 140 string operations_[] = {"add u 1", "change u b 100", "change a b 2"}; > 141 vector <string> operations(operations_, operations_+sizeof(operations_ > 142 int _ = 103; > 143 END > 144 CASE(7) // killer! > 145 string word = "az"; > 146 string operations_[] = {"add b 1", "change a b 1"}; > 147 vector <string> operations(operations_, operations_+sizeof(operations_ > 148 int _ = 2; > 149 END > 150 } > 151 // END CUT HERE