Overview
| SHA1 Hash: | c009363094fcb7a2b91a11159dd184cfb9f86809 |
|---|---|
| Date: | 2013-04-06 14:43:56 |
| User: | kinaba |
| Comment: | TCOR2A |
| 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/TCO13-2A-U/1A.cpp version [8773ddd5052442db]
> 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<LD> CMP; > 21 > 22 template<typename T> > 23 struct DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 class TheLargestString { public: > 36 string find(string s, string t) > 37 { > 38 const int N = s.size(); > 39 DP2< pair<string,string> > best(N+1,N+1); > 40 for(int i=N-1; i>=0; --i) > 41 { > 42 for(int len=1; len<=N-i; ++len) > 43 { > 44 pair<string, string> cand = best(i+1, len); > 45 pair<string, string> cand2(s[i]+best(i+1, len-1) > 46 if(cand.first+cand.second < cand2.first+cand2.se > 47 cand = cand2; > 48 best(i, len) = cand; > 49 } > 50 } > 51 string ans; > 52 for(int len=0; len<=N; ++len) > 53 ans = max(ans, best(0,len).first + best(0,len).second); > 54 return ans; > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const string& Expected, const string& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, TheLargestString().find(s, t));} > 72 int main(){ > 73 CASE(0) > 74 string s = "ab"; > 75 string t = "zy"; > 76 string _ = "by"; > 77 END > 78 CASE(1) > 79 string s = "abacaba"; > 80 string t = "zzzaaaa"; > 81 string _ = "cbaaaa"; > 82 END > 83 CASE(2) > 84 string s = "x"; > 85 string t = "x"; > 86 string _ = "xx"; > 87 END > 88 CASE(3) > 89 string s = "abbabbabbababaaaabbababab"; > 90 string t = "bababbaabbbababbbbababaab"; > 91 string _ = "bbbbbbbbbbbbbbbbbbaaab"; > 92 END > 93 /* > 94 CASE(4) > 95 string s = ; > 96 string t = ; > 97 string _ = ; > 98 END > 99 CASE(5) > 100 string s = ; > 101 string t = ; > 102 string _ = ; > 103 END > 104 */ > 105 } > 106 // END CUT HERE
Added SRM/TCO13-2A-U/1C-U.cpp version [5a2518f603d02674]
> 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<LD> CMP; > 21 > 22 class ThePowers { public: > 23 long long find(int A, int B) > 24 { > 25 LL total = 1; > 26 > 27 int prev_cnt = 1; > 28 for(int K=31; K>=1; --K) > 29 { > 30 int ub = invpow(A,K); > 31 int cnt = num_ppprime_under(ub); > 32 LL x = solve2(K,B) * (cnt - prev_cnt); > 33 total += x; > 34 prev_cnt = cnt; > 35 } > 36 return total; > 37 } > 38 > 39 // max x s.t. x^K <= A; > 40 int invpow(int A, int K) > 41 { > 42 int v = 0; > 43 int c = (int)pow(A, 1.0/K); > 44 for(int x=max(1,c-3); x<=c+3; ++x) > 45 if( pow_leq(x, K, A) ) > 46 v = x; > 47 return v; > 48 } > 49 > 50 // number of non-square, cubic, ... numbers in [1,N] > 51 int num_ppprime_under(int N) > 52 { > 53 int total = N; > 54 vector<int> num(32); > 55 for(int p=num.size()-1; p>=2; --p) > 56 { > 57 num[p] = invpow(N, p) - 1; > 58 for(int q=p+p; q<num.size(); q+=p) > 59 num[p] -= num[q]; > 60 total -= num[p]; > 61 } > 62 return total; > 63 } > 64 > 65 int pow_leq(int x, int p, int N) > 66 { > 67 LL v = 1; > 68 for(int i=0; i<p; ++i) { > 69 v *= x; > 70 if(v>N) > 71 return false; > 72 } > 73 return true; > 74 } > 75 > 76 // number of [1,K]*[1,B] > 77 LL solve2(int K, int B) > 78 { > 79 set<LL> test; > 80 for(LL x=1; x<=K; ++x) > 81 for(LL y=1; y<=B; ++y) > 82 test.insert(x*y); > 83 return test.size(); > 84 } > 85 }; > 86 > 87 // BEGIN CUT HERE > 88 #include <ctime> > 89 double start_time; string timer() > 90 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 91 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 92 { os << "{ "; > 93 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 94 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 95 void verify_case(const long long& Expected, const long long& Received) { > 96 bool ok = (Expected == Received); > 97 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 98 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 99 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 100 #define END verify_case(_, ThePowers().find(A, B));} > 101 int main(){ > 102 > 103 CASE(0) > 104 int A = 7; > 105 int B = 4; > 106 long long _ = 23LL; > 107 END > 108 CASE(1) > 109 int A = 1; > 110 int B = 1; > 111 long long _ = 1LL; > 112 END > 113 CASE(2) > 114 int A = 1000000000; > 115 int B = 1000000000; > 116 long long _ = 999983644283653287LL; > 117 END > 118 CASE(3) > 119 int A = 999999999; > 120 int B = 5; > 121 long long _ = 4999934406LL; > 122 END > 123 /* > 124 CASE(4) > 125 int A = ; > 126 int B = ; > 127 long long _ = LL; > 128 END > 129 CASE(5) > 130 int A = ; > 131 int B = ; > 132 long long _ = LL; > 133 END > 134 */ > 135 } > 136 // END CUT HERE