Overview
| SHA1 Hash: | 4977026daf568a86b809ba8092eb9bd7e68526d1 |
|---|---|
| Date: | 2012-01-14 16:37:31 |
| User: | kinaba |
| Comment: | 428 |
| 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/428/2A.cpp version [8837192db915bbc6]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class ThePalindrome { public: > 29 int find(string s) > 30 { > 31 for(int i=0; i<s.size(); ++i) > 32 if( is_palin(s + string(s.rbegin()+(s.size()-i), s.rend( > 33 return i + s.size(); > 34 return s.size() * 2; > 35 } > 36 > 37 bool is_palin(const string& s) { > 38 return s == string(s.rbegin(), s.rend()); > 39 } > 40 }; > 41 > 42 // BEGIN CUT HERE > 43 #include <ctime> > 44 double start_time; string timer() > 45 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 46 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 47 { os << "{ "; > 48 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 49 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 50 void verify_case(const int& Expected, const int& Received) { > 51 bool ok = (Expected == Received); > 52 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 53 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 54 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 55 #define END verify_case(_, ThePalindrome().find(s));} > 56 int main(){ > 57 > 58 CASE(0) > 59 string s = "abab"; > 60 int _ = 5; > 61 END > 62 CASE(1) > 63 string s = "abacaba"; > 64 int _ = 7; > 65 END > 66 CASE(2) > 67 string s = "qwerty"; > 68 int _ = 11; > 69 END > 70 CASE(3) > 71 string s = "abdfhdyrbdbsdfghjkllkjhgfds"; > 72 int _ = 38; > 73 END > 74 /* > 75 CASE(4) > 76 string s = ; > 77 int _ = ; > 78 END > 79 CASE(5) > 80 string s = ; > 81 int _ = ; > 82 END > 83 */ > 84 } > 85 // END CUT HERE
Added SRM/428/2C.cpp version [6285086493d4d598]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class TheDictionary { public: > 29 string find(int n, int m, int k) > 30 { > 31 if( k <= C(n+m,n) ) > 32 return rec(n, m, k); > 33 return ""; > 34 } > 35 > 36 string rec(int n, int m, int k) > 37 { > 38 if( n+m == 0 ) > 39 return ""; > 40 if( n==0 ) > 41 return "z" + rec(n, m-1, k); > 42 if( m==0 ) > 43 return "a" + rec(n-1, m, k); > 44 > 45 LL c = C(n+m-1, m); > 46 if( k <= c ) > 47 return "a" + rec(n-1, m, k); > 48 return "z" + rec(n, m-1, k - c); > 49 } > 50 > 51 LL C(int n, int k) > 52 { > 53 k = min(k, n-k); > 54 LL v = 1; > 55 for(int i=1; i<=k; ++i) { > 56 v = v * (n+1-i) / i; > 57 if( v >= (1LL<<50) ) > 58 return v; > 59 } > 60 return v; > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const string& Expected, const string& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, TheDictionary().find(n, m, k));} > 78 int main(){ > 79 > 80 CASE(0) > 81 int n = 2; > 82 int m = 2; > 83 int k = 2; > 84 string _ = "azaz"; > 85 END > 86 CASE(1) > 87 int n = 2; > 88 int m = 2; > 89 int k = 6; > 90 string _ = "zzaa"; > 91 END > 92 CASE(2) > 93 int n = 10; > 94 int m = 10; > 95 int k = 1000000000; > 96 string _ = ""; > 97 END > 98 CASE(3) > 99 int n = 7; > 100 int m = 4; > 101 int k = 47; > 102 string _ = "aaazazaazaz"; > 103 END > 104 /* > 105 CASE(4) > 106 int n = ; > 107 int m = ; > 108 int k = ; > 109 string _ = ; > 110 END > 111 CASE(5) > 112 int n = ; > 113 int m = ; > 114 int k = ; > 115 string _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE