Overview
| SHA1 Hash: | d3b1273780052dca025abb3b3f35a023009b03fb |
|---|---|
| Date: | 2014-06-12 14:49:12 |
| User: | kinaba |
| Comment: | TCO14 2B |
| 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/TCO14-2B-U/1A.cpp version [1d275d88bba6cbca]
> 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 SwitchingGame { public: > 23 int timeToWin(vector <string> states) > 24 { > 25 const int W = states[0].size(); > 26 string cur(W, '-'); > 27 > 28 int sec = 0; > 29 for(int i=0; i<states.size(); ++i) > 30 { > 31 bool need_flip_to_minus = false; > 32 bool need_flip_to_plus = false; > 33 for(int k=0; k<W; ++k) { > 34 if(states[i][k]=='-' && cur[k]=='+') > 35 need_flip_to_minus = true; > 36 if(states[i][k]=='+' && cur[k]=='-') > 37 need_flip_to_plus = true; > 38 } > 39 > 40 for(int k=0; k<W; ++k) { > 41 switch(states[i][k]) > 42 { > 43 case '-': > 44 cur[k] = '-'; > 45 break; > 46 case '+': > 47 cur[k] = '+'; > 48 break; > 49 case '?': > 50 for(int j=i+1; j<states.size(); ++j) { > 51 if(states[j][k]=='-') {if(need_f > 52 if(states[j][k]=='+') {if(need_f > 53 } > 54 break; > 55 } > 56 } > 57 sec += 1 + need_flip_to_plus + need_flip_to_minus; > 58 } > 59 return sec; > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, SwitchingGame().timeToWin(states));} > 77 int main(){ > 78 > 79 CASE(1) > 80 string states_[] = {"+-++", > 81 "+-++"}; > 82 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 83 int _ = 3; > 84 END > 85 CASE(0) > 86 string states_[] = {"++--", > 87 "--++"}; > 88 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 89 int _ = 5; > 90 END > 91 CASE(2) > 92 string states_[] = {"++", > 93 "+?", > 94 "?+", > 95 "++"}; > 96 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 97 int _ = 5; > 98 END > 99 CASE(3) > 100 string states_[] = {"+", > 101 "?", > 102 "?", > 103 "?", > 104 "-"}; > 105 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 106 int _ = 7; > 107 END > 108 CASE(4) > 109 string states_[] = {"+??+++", > 110 "++??+-", > 111 "?++??+", > 112 "?-+-??", > 113 "??+?++", > 114 "++-?+?", > 115 "?++?-+", > 116 "?--+++", > 117 "-??-?+"} > 118 ; > 119 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 120 int _ = 20; > 121 END > 122 /* > 123 CASE(5) > 124 string states_[] = ; > 125 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 126 int _ = ; > 127 END > 128 CASE(6) > 129 string states_[] = ; > 130 vector <string> states(states_, states_+sizeof(states_)/sizeof(*states > 131 int _ = ; > 132 END > 133 */ > 134 } > 135 // END CUT HERE
Added SRM/TCO14-2B-U/1B.cpp version [d6a6dfb9fe6aa739]
> 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 SumAndProductPuzzle { public: > 23 long long getSum(int A, int B) > 24 { > 25 static const int N = 5000000; > 26 vector<bool> isp(N+1, true); > 27 for(int p=2; p<=N; ++p) > 28 if(isp[p]) > 29 for(int q=p+p; q<=N; q+=p) > 30 isp[q] = false; > 31 > 32 vector<bool> has_dec(N+1, false); > 33 for(int p=2; p<=N; ++p) > 34 for(int S=p+p; S<=N; S+=p) { > 35 int q = S/p; > 36 if(!isp[p+q-1]) > 37 has_dec[S] = true; > 38 } > 39 > 40 LL sum = 0; > 41 for(int S=A; S<=B; ++S) > 42 if(!isp[S-1] && !has_dec[S-1]) > 43 sum += S; > 44 return sum; > 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 long long& Expected, const long long& Received) { > 57 bool ok = (Expected == Received); > 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 61 #define END verify_case(_, SumAndProductPuzzle().getSum(A, B));} > 62 int main(){ > 63 > 64 CASE(0) > 65 int A = 30; > 66 int B = 33; > 67 long long _ = 33LL; > 68 END > 69 CASE(1) > 70 int A = 8; > 71 int B = 11; > 72 long long _ = 19LL; > 73 END > 74 CASE(2) > 75 int A = 40; > 76 int B = 43; > 77 long long _ = 0LL; > 78 END > 79 CASE(3) > 80 int A = 47; > 81 int B = 74; > 82 long long _ = 168LL; > 83 END > 84 CASE(4) > 85 int A = 1; > 86 int B = 2; > 87 long long _ = 0LL; > 88 END > 89 CASE(5) > 90 int A = 1; > 91 int B = 5000000; > 92 long long _ = -1LL; > 93 END > 94 CASE(6) > 95 int A = 1; > 96 int B = 1; > 97 long long _ = 0LL; > 98 END > 99 } > 100 // END CUT HERE
Added SRM/TCO14-2B-U/1C-U.cpp version [0f5c0e345a533ed4]
> 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 AlwaysDefined { public: > 23 long long countIntegers(long long L, long long R, int W) > 24 { > 25 vector<vector<int>> tbl(W); > 26 for(int q=1; q<=W-1; ++q) > 27 for(int r=1; r<=W-1; ++r) > 28 if(q*r%W == r) > 29 tbl[q].push_back(r); > 30 > 31 // count all numbers that can be generated by repeating > 32 // x ==> rx where tbl[x%W].has(r) > 33 if(R<=1000000) > 34 { > 35 vector<int> V(R+1, false); > 36 for(int k=0; k*W+1<=R; ++k) > 37 { > 38 queue<int> Q; > 39 if(!V[k*W+1]) > 40 Q.push(k*W+1), V[k*W+1]=true; > 41 while(!Q.empty()) > 42 { > 43 int s = Q.front(); > 44 Q.pop(); > 45 for(int r: tbl[s%W]) { > 46 if(s*r<=R && !V[s*r]) > 47 Q.push(s*r), V[s*r]=true > 48 } > 49 } > 50 } > 51 LL cnt = 0; > 52 for(LL X=L; X<=R; ++X) > 53 if(V[X]) > 54 ++cnt; > 55 return cnt; > 56 } > 57 > 58 > 59 LL cnt = 0; > 60 for(LL X=L; X<=R; ++X) > 61 { > 62 LL x = X; > 63 for(;;) { > 64 if(x%W==0) > 65 break; > 66 if(x%W==1) > 67 {++cnt; break;} > 68 if(x%(x%W)!=0) > 69 break; > 70 x /= x%W; > 71 } > 72 } > 73 return cnt; > 74 } > 75 }; > 76 > 77 // BEGIN CUT HERE > 78 #include <ctime> > 79 double start_time; string timer() > 80 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 81 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 82 { os << "{ "; > 83 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 84 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 85 void verify_case(const long long& Expected, const long long& Received) { > 86 bool ok = (Expected == Received); > 87 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 89 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 90 #define END verify_case(_, AlwaysDefined().countIntegers(L, R, W));} > 91 int main(){ > 92 > 93 CASE(0) > 94 long long L = 10LL; > 95 long long R = 10LL; > 96 int W = 4; > 97 long long _ = 1LL; > 98 END > 99 CASE(1) > 100 long long L = 1LL; > 101 long long R = 99LL; > 102 int W = 2; > 103 long long _ = 50LL; > 104 END > 105 CASE(2) > 106 long long L = 1282LL; > 107 long long R = 1410LL; > 108 int W = 10; > 109 long long _ = 42LL; > 110 END > 111 CASE(178116) > 112 long long L = 1LL; > 113 long long R = 1000000LL; > 114 int W = 30; > 115 long long _ = 154161LL; > 116 END > 117 CASE(3) > 118 long long L = 29195807LL; > 119 long long R = 273209804877LL; > 120 int W = 42; > 121 long long _ = 31415926535LL; > 122 END > 123 CASE(4) > 124 long long L = 1LL; > 125 long long R = 1000000000000000000LL; > 126 int W = 3000; > 127 long long _ = -1LL; > 128 END > 129 CASE(5) > 130 long long L = 1LL; > 131 long long R = 1000000000000000000LL; > 132 int W = 3; > 133 long long _ = -1LL; > 134 END > 135 } > 136 // END CUT HERE