Overview
| SHA1 Hash: | 26aa079da886ac49ead91b2d661ba49dbef0e848 |
|---|---|
| Date: | 2015-01-02 11:40:47 |
| User: | kinaba |
| Comment: | 643 |
| 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/643-U/1A.cpp version [275bf68bac256758]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheKingsFactorization { public: > 23 vector<long long> getVector(long long N, vector<long long> primes) > 24 { > 25 vector<LL> ans; > 26 for(int p=2; p<=1000001; ++p) > 27 while(N%p == 0) { > 28 ans.push_back(p); > 29 N /= p; > 30 } > 31 > 32 // all primes <= cbrt(N) is reported. we have at most 2 more. > 33 > 34 const LL last_p = primes.back(); > 35 if(N%last_p==0 && N!=last_p) { > 36 ans.push_back(min(N/last_p, last_p)); > 37 ans.push_back(max(N/last_p, last_p)); > 38 N = 1; > 39 } > 40 > 41 if(N!=1) > 42 ans.push_back(N); > 43 > 44 return ans; > 45 } > 46 }; > 47 > 48 // BEGIN CUT HERE > 49 #include <ctime> > 50 double start_time; string timer() > 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 52 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 53 { os << "{ "; > 54 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 55 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 56 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 57 bool ok = (Expected == Received); > 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 59 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 61 #define END verify_case(_, TheKingsFactorization().getVector(N, primes));} > 62 int main(){ > 63 > 64 CASE(0) > 65 long long N = 12LL; > 66 long long primes_[] = {2, 3}; > 67 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 68 long long __[] = {2, 2, 3 }; > 69 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 70 END > 71 CASE(1) > 72 long long N = 7LL; > 73 long long primes_[] = {7}; > 74 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 75 long long __[] = {7 }; > 76 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 77 END > 78 CASE(2) > 79 long long N = 1764LL; > 80 long long primes_[] = {2, 3, 7}; > 81 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 82 long long __[] = {2, 2, 3, 3, 7, 7 }; > 83 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 84 END > 85 CASE(3) > 86 long long N = 49LL; > 87 long long primes_[] = {7}; > 88 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 89 long long __[] = {7, 7 }; > 90 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 91 END > 92 CASE(4) > 93 long long N = 210LL; > 94 long long primes_[] = {2, 5}; > 95 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 96 long long __[] = {2, 3, 5, 7 }; > 97 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 98 END > 99 CASE(5) > 100 long long N = 100000LL; > 101 long long primes_[] = {2, 2, 2, 5, 5}; > 102 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 103 long long __[] = {2, 2, 2, 2, 2, 5, 5, 5, 5, 5 }; > 104 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(6) > 107 long long N = 540000003780LL; > 108 long long primes_[] = {2,3,3,1000000007}; > 109 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 110 long long __[] = {2,2,3,3,3,5,1000000007}; > 111 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 112 END > 113 CASE(7) > 114 long long N = 2700000018900LL; > 115 long long primes_[] = {2,3,3,5}; > 116 vector<long long> primes(primes_, primes_+sizeof(primes_)/sizeof(*prim > 117 long long __[] = {2,2,3,3,3,5,5,1000000007}; > 118 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 119 END > 120 } > 121 // END CUT HERE
Added SRM/643-U/1B-U.cpp version [f8183ab5eda22bf1]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 enum {HH, HS, SH, SS}; > 23 > 24 class TheKingsArmyDiv1 { public: > 25 int getNumber(vector <string> state) > 26 { > 27 const int N = state[0].size(); > 28 > 29 vector<int> s; > 30 for(int i=0; i<N; ++i) > 31 s.push_back((state[0][i]=='S')*2 + (state[1][i]=='S')); > 32 > 33 const int nSS = count(s.begin(), s.end(), SS); > 34 if(nSS == N) > 35 return -1; > 36 > 37 vector<vector<int>> blocks; > 38 for(int i=0; i<N; ) { > 39 while(i<N && s[i]==SS) ++i; > 40 if(i<N) { > 41 blocks.emplace_back(); > 42 while(i<N && s[i]!=SS) { > 43 if(s[i] != HH) > 44 blocks.back().push_back(s[i]); > 45 ++i; > 46 } > 47 if(blocks.back().empty()) > 48 blocks.pop_back(); > 49 } > 50 } > 51 > 52 int c1=0, c2=0; > 53 for(auto& bl: blocks) { > 54 c1 += align_cost(bl, HS); > 55 c2 += align_cost(bl, SH); > 56 } > 57 return nSS + (blocks.empty() ? 0 : min(c1, c2)+1); > 58 } > 59 > 60 int align_cost(const vector<int>& b, int type) > 61 { > 62 int cost = 0; > 63 for(int i=0; i<b.size(); ) { > 64 while(i<b.size() && b[i]==type) ++i; > 65 if(i<b.size()) { > 66 while(i<b.size() && b[i]!=type) ++i; > 67 ++cost; > 68 } > 69 } > 70 return cost; > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const int& Expected, const int& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, TheKingsArmyDiv1().getNumber(state));} > 88 int main(){ > 89 > 90 CASE(0) > 91 string state_[] = {"HSH", > 92 "SHS"}; > 93 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 94 int _ = 2; > 95 END > 96 CASE(1) > 97 string state_[] = {"HH", > 98 "HH"}; > 99 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 100 int _ = 0; > 101 END > 102 CASE(2) > 103 string state_[] = {"HHHHH", > 104 "HSHSH"}; > 105 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 106 int _ = 1; > 107 END > 108 CASE(3) > 109 string state_[] = {"S", > 110 "S"}; > 111 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 112 int _ = -1; > 113 END > 114 CASE(4) > 115 string state_[] = {"HSHHSHSHSHHHSHSHSH", > 116 "SSSSHSSHSHSHHSSSSH"}; > 117 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 118 int _ = 8; > 119 END > 120 CASE(5) > 121 string state_[] = {"HS", > 122 "HS"}; > 123 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 124 int _ = 1; > 125 END > 126 CASE(6) > 127 string state_[] = {"HHH", "SSS"}; > 128 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 129 int _ = 1; > 130 END > 131 /* > 132 CASE(7) > 133 string state_[] = ; > 134 vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); > 135 int _ = ; > 136 END > 137 */ > 138 } > 139 // END CUT HERE