Overview
| SHA1 Hash: | 7e18a763ef3c40f9bc2cb3095ab025361fd727b8 |
|---|---|
| Date: | 2013-01-29 14:39:14 |
| User: | kinaba |
| Comment: | 567 |
| 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/567-U/1A-U.cpp version [d3ffd1bee1dc3b17]
> 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 TheSquareRootDilemma { public: > 23 int countPairs(int N, int M) > 24 { > 25 static const int X = 279; > 26 vector<bool> isp(X+1, true); > 27 vector<int> ps; > 28 for(int p=2; p<=X; ++p) > 29 if( isp[p] ) { > 30 ps.push_back(p); > 31 for(int q=p+p; q<=X; q+=p) > 32 isp[q] = false; > 33 } > 34 > 35 map<vector<int>, int> AA; > 36 for(int A=1; A<=N; ++A) > 37 { > 38 int x = A; > 39 vector<int> v; > 40 for(int i=0; i<ps.size(); ++i) { > 41 int p = ps[i]; > 42 int k = 0; > 43 while(x%p==0) {k++; x/=p;} > 44 v.push_back(k&1); > 45 } > 46 if(x==1) > 47 AA[v]++; > 48 } > 49 > 50 int result = 0; > 51 for(int B=1; B<=M; ++B) > 52 { > 53 int x = B; > 54 vector<int> v; > 55 for(int i=0; i<ps.size(); ++i) { > 56 int p = ps[i]; > 57 int k = 0; > 58 while(x%p==0) {k++; x/=p;} > 59 v.push_back(k&1); > 60 } > 61 if(x==1) > 62 result += AA[v]; > 63 } > 64 return result; > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const int& Expected, const int& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, TheSquareRootDilemma().countPairs(N, M));} > 82 int main(){ > 83 > 84 CASE(0) > 85 int N = 2; > 86 int M = 2; > 87 int _ = 2; > 88 END > 89 CASE(1) > 90 int N = 10; > 91 int M = 1; > 92 int _ = 3; > 93 END > 94 CASE(2) > 95 int N = 3; > 96 int M = 8; > 97 int _ = 5; > 98 END > 99 CASE(3) > 100 int N = 100; > 101 int M = 100; > 102 int _ = 310; > 103 END > 104 CASE(4) > 105 int N = 77777; > 106 int M = 77777; > 107 int _ = -1; > 108 END > 109 /* > 110 CASE(5) > 111 int N = ; > 112 int M = ; > 113 int _ = ; > 114 END > 115 */ > 116 } > 117 // END CUT HERE
Added SRM/567-U/1B.cpp version [12cbf48a8719e317]
> 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 StringGame { public: > 23 vector <int> getWinningStrings(vector <string> S) > 24 { > 25 vector< vector<int> > cb; > 26 for(int i=0; i<S.size(); ++i) > 27 cb.push_back(as_cb(S[i])); > 28 > 29 vector<int> result; > 30 for(int i=0; i<cb.size(); ++i) > 31 if( can_win(cb, i) ) > 32 result.push_back(i); > 33 return result; > 34 } > 35 > 36 vector<int> as_cb(const string& s) > 37 { > 38 vector<int> cb(26); > 39 for(int i=0; i<s.size(); ++i) > 40 cb[s[i]-'a']++; > 41 return cb; > 42 } > 43 > 44 bool can_win(const vector< vector<int> >& cb, int I) > 45 { > 46 vector<int> enemy; > 47 for(int i=0; i<cb.size(); ++i) > 48 if(i != I) > 49 enemy.push_back(i); > 50 > 51 while(!enemy.empty()) > 52 { > 53 bool update = false; > 54 for(int c=0; c<26; ++c) > 55 { > 56 vector<int> win, draw; > 57 for(int i=0; i<enemy.size(); ++i) > 58 { > 59 int e = enemy[i]; > 60 if(cb[e][c] < cb[I][c]) > 61 win.push_back(e); > 62 else if(cb[e][c] == cb[I][c]) > 63 draw.push_back(e); > 64 } > 65 if(!win.empty() && win.size() + draw.size() == e > 66 enemy = draw; > 67 update = true; > 68 } > 69 } > 70 if(!update) > 71 return false; > 72 } > 73 > 74 return true; > 75 } > 76 }; > 77 > 78 // BEGIN CUT HERE > 79 #include <ctime> > 80 double start_time; string timer() > 81 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 82 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 83 { os << "{ "; > 84 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 85 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 86 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 87 bool ok = (Expected == Received); > 88 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 89 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 90 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 91 #define END verify_case(_, StringGame().getWinningStrings(S));} > 92 int main(){ > 93 > 94 CASE(0) > 95 string S_[] = {"a", "b", "c", "d"}; > 96 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 97 int __[] = {0, 1, 2, 3 }; > 98 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 99 END > 100 CASE(1) > 101 string S_[] = {"aabbcc", "aaabbb", "aaaccc"}; > 102 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 103 int __[] = {1, 2 }; > 104 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(2) > 107 string S_[] = {"ab", "ba"}; > 108 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 109 vector <int> _; > 110 END > 111 CASE(3) > 112 string S_[] = {"xaocxsss", "oooxsoas", "xaooosss", "xaocssss", "coxaosxx > 113 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 114 int __[] = {1, 3, 4 }; > 115 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 116 END > 117 CASE(4) > 118 string S_[] = {"aaabbc", "aabbcc", "aaaabc"}; > 119 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 120 int __[] = {0, 1, 2}; > 121 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 122 END > 123 /* > 124 CASE(5) > 125 string S_[] = ; > 126 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 127 int __[] = ; > 128 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 129 END > 130 */ > 131 } > 132 // END CUT HERE
Added SRM/567-U/1C.cpp version [4557c7ca92985007]
> 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 static const unsigned MODVAL = 1000000009; > 23 > 24 class Mountains { public: > 25 int countPlacements(vector <int> heights, vector <string> visibility) > 26 { > 27 int W = visibility[0].size(); > 28 int N = visibility.size(); > 29 memo.resize(N); > 30 > 31 vector<int> view(W, 0); > 32 return rec(W, view, heights.size()-1, heights, visibility); > 33 } > 34 > 35 vector< map<vector<int>,int> > memo; > 36 int rec(int W, const vector<int>& view, int i, vector<int>& H, const vec > 37 { > 38 if(i < 0) > 39 return 1; > 40 > 41 if(memo[i].count(view)) > 42 return memo[i][view]; > 43 > 44 int mustL=0, mustR=W-1; > 45 int mustNotL=W, mustNotR=-1; > 46 for(int x=0; x<W; ++x) > 47 { > 48 int LLL = x - (H[i]-view[x]-1); > 49 int RRR = x + (H[i]-view[x]-1); > 50 if(V[i][x] == 'X') { > 51 if( H[i] <= view[x] ) > 52 return 0; > 53 mustL = max(mustL, LLL); > 54 mustR = min(mustR, RRR); > 55 } else { > 56 // if( H[i] > view[x] ) { > 57 // mustNotL = min(mustNotL, LLL); > 58 // mustNotR = max(mustNotR, RRR); > 59 // } > 60 } > 61 } > 62 > 63 LL result = 0; > 64 for(int c=mustL; c<=mustR; ++c) if(c<mustNotL || mustNotR<c) > 65 { > 66 bool good = true; > 67 for(int x=0; x<W && good; ++x) { > 68 int my_h = H[i] - abs(x-c); > 69 if((V[i][x]=='X') != (view[x] < my_h)) > 70 good = false; > 71 } > 72 > 73 if( good ) { > 74 vector<int> view2(W); > 75 for(int x=0; x<W; ++x) { > 76 int my_h = H[i] - abs(x-c); > 77 view2[x] = max(my_h, view[x]); > 78 } > 79 result += rec(W, view2, i-1, H, V); > 80 } > 81 } > 82 return memo[i][view] = int(result % MODVAL); > 83 } > 84 }; > 85 > 86 // BEGIN CUT HERE > 87 #include <ctime> > 88 double start_time; string timer() > 89 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 90 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 91 { os << "{ "; > 92 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 93 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 94 void verify_case(const int& Expected, const int& Received) { > 95 bool ok = (Expected == Received); > 96 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 97 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 98 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 99 #define END verify_case(_, Mountains().countPlacements(heights, visibility) > 100 int main(){ > 101 > 102 CASE(0) > 103 int heights_[] = {2, 3, 2}; > 104 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 105 string visibility_[] = {"------", > 106 "XXXX--", > 107 "---XXX"}; > 108 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 109 int _ = 4; > 110 END > 111 CASE(1) > 112 int heights_[] = {4, 3, 4}; > 113 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 114 string visibility_[] = {"XXXXX--------", > 115 "----------XXX", > 116 "----XXXXXXX--"}; > 117 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 118 int _ = 4; > 119 END > 120 CASE(2) > 121 int heights_[] = {13, 2, 3, 2}; > 122 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 123 string visibility_[] = {"XXXXXXXXX", > 124 "-XXX-----", > 125 "----XXXXX", > 126 "-----XXX-"}; > 127 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 128 int _ = 9; > 129 END > 130 CASE(3) > 131 int heights_[] = {8, 2, 9, 3, 10}; > 132 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 133 string visibility_[] = {"X------", > 134 "-------", > 135 "------X", > 136 "-------", > 137 "XXXXXXX"}; > 138 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 139 int _ = 98; > 140 END > 141 CASE(4) > 142 int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50}; > 143 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 144 string visibility_[] = {"-------------------", > 145 "-------------------", > 146 "-------------------", > 147 "-------------------", > 148 "-------------------", > 149 "-------------------", > 150 "-------------------", > 151 "------------XXXXXXX", > 152 "XXXXXXX------------", > 153 "XXXXXXXXXXXXXXXXXXX"} > 154 ; > 155 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 156 int _ = 973726691; > 157 END > 158 CASE(5) > 159 int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50}; > 160 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 161 string visibility_[] = {"----------------------------------------------- > 162 "-------------------------------------------------", > 163 "-------------------------------------------------", > 164 "-------------------------------------------------", > 165 "-------------------------------------------------", > 166 "-------------------------------------------------", > 167 "-------------------------------------------------", > 168 "------------XXXXXXX------------------------------", > 169 "XXXXXXX------------------------------------------", > 170 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"} > 171 ; > 172 vector <string> visibility(visibility_, visibility_+sizeof(visibility_ > 173 int _ = -1; > 174 END > 175 } > 176 // END CUT HERE