Overview
| SHA1 Hash: | 8ca6d3c2884c387bdde4dabefcff12f1308804fe |
|---|---|
| Date: | 2013-12-15 07:33:04 |
| User: | kinaba |
| Comment: | 600 |
| 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/600-U/1A.cpp version [8f0cc3f762f50033]
> 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 ORSolitaire { public: > 23 int getMinimum(vector <int> numbers, int goal) > 24 { > 25 vector<int> n2; > 26 for(int u: numbers) > 27 if((goal&u) == u) > 28 n2.push_back(u); > 29 numbers.swap(n2); > 30 > 31 int best = 9999999; > 32 for(int v=1; v<=goal; v<<=1) if(goal&v) { > 33 int cnt = 0; > 34 for(int u: numbers) > 35 if(u&v) > 36 ++cnt; > 37 best = min(best, cnt); > 38 } > 39 return best; > 40 } > 41 }; > 42 > 43 // BEGIN CUT HERE > 44 #include <ctime> > 45 double start_time; string timer() > 46 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 47 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 48 { os << "{ "; > 49 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 50 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 51 void verify_case(const int& Expected, const int& Received) { > 52 bool ok = (Expected == Received); > 53 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 55 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 56 #define END verify_case(_, ORSolitaire().getMinimum(numbers, goal));} > 57 int main(){ > 58 > 59 CASE(0) > 60 int numbers_[] = {1, 2, 4}; > 61 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 62 int goal = 7; > 63 int _ = 1; > 64 END > 65 CASE(1) > 66 int numbers_[] = {1, 2, 4, 7, 8}; > 67 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 68 int goal = 7; > 69 int _ = 2; > 70 END > 71 CASE(2) > 72 int numbers_[] = {12571295, 2174218, 2015120}; > 73 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 74 int goal = 1; > 75 int _ = 0; > 76 END > 77 CASE(3) > 78 int numbers_[] = {5,2,4,52,62,9,8,3,1,11,6}; > 79 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 80 int goal = 11; > 81 int _ = 3; > 82 END > 83 CASE(4) > 84 int numbers_[] = {503, 505, 152, 435, 491, 512, 1023, 355, 510, 500, 502 > 85 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 86 int goal = 510; > 87 int _ = 5; > 88 END > 89 CASE(5) > 90 int numbers_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21, > 91 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 92 int goal = 63; > 93 int _ = 19; > 94 END > 95 /* > 96 CASE(6) > 97 int numbers_[] = ; > 98 vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbe > 99 int goal = ; > 100 int _ = ; > 101 END > 102 */ > 103 } > 104 // END CUT HERE
Added SRM/600-U/1B.cpp version [3ba15225dab415f3]
> 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 PalindromeMatrix { public: > 23 int minChange(vector <string> A, int rowCount, int columnCount) > 24 { > 25 const int H = A.size(), W = A[0].size(); > 26 vector<vector<int>> cpp, rpp; > 27 { > 28 vector<int> cp(W-columnCount, 0); cp.resize(W, 1); > 29 do cpp.push_back(cp); while(next_permutation(cp.begin(), > 30 vector<int> rp(H-rowCount, 0); rp.resize(H, 1); > 31 do rpp.push_back(rp); while(next_permutation(rp.begin(), > 32 } > 33 > 34 int best = 99999999; > 35 for(auto& cp: cpp) > 36 { > 37 int c_score = 0; > 38 for(int x=0; x<W; ++x) if(cp[x]) > 39 for(int y=0; y<H-1-y; ++y) > 40 c_score += maj(A[y][x], A[H-1-y][x]); > 41 > 42 vector<int> r_score_0(H), r_score_3(H), r_score_4(H); > 43 for(int y=0; y<H; ++y) > 44 for(int x=0; x<W-1-x; ++x) > 45 if(!cp[x] && !cp[W-1-x]) { > 46 r_score_0[y] += maj(A[y][x], A[y > 47 r_score_3[y] += maj(A[y][x], A[y > 48 r_score_4[y] += maj(A[y][x], A[y > 49 } else { > 50 if(cp[x] && cp[W-1-x]) > 51 r_score_3[y] += maj(A[y] > 52 - maj(A[y][x],A[ > 53 else if(cp[x]) > 54 r_score_3[y] += maj(A[y] > 55 else > 56 r_score_3[y] += maj(A[y] > 57 r_score_4[y] += maj(A[y][x],A[H- > 58 - (cp[x] ? maj(A[y][x],A > 59 } > 60 > 61 for(auto& rp: rpp) { > 62 int score = c_score; > 63 for(int y=0; y<H; ++y) if(rp[y]) { > 64 if(!rp[H-1-y]) score += r_score_3[y]; > 65 else score += (y<H-1-y ? r_score_4 : r_s > 66 } > 67 best = min(best, score); > 68 } > 69 } > 70 return best; > 71 } > 72 > 73 static int maj(char a, char b, char c, char d) { > 74 int cnt = (a=='0')+(b=='0')+(c=='0')+(d=='0'); > 75 return cnt<2?cnt:4-cnt; > 76 } > 77 static int maj(char a, char b, char c) { > 78 int cnt = (a=='0')+(b=='0')+(c=='0'); > 79 return cnt<2?cnt:3-cnt; > 80 } > 81 static int maj(char a, char b) { > 82 return a!=b; > 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(_, PalindromeMatrix().minChange(A, rowCount, column > 100 int main(){ > 101 > 102 CASE(0) > 103 string A_[] = {"0000" > 104 ,"1000" > 105 ,"1100" > 106 ,"1110"}; > 107 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 108 int rowCount = 2; > 109 int columnCount = 2; > 110 int _ = 1; > 111 END > 112 CASE(1) > 113 string A_[] = {"0000" > 114 ,"1000" > 115 ,"1100" > 116 ,"1110"}; > 117 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 118 int rowCount = 3; > 119 int columnCount = 2; > 120 int _ = 3; > 121 END > 122 CASE(2) > 123 string A_[] = {"01" > 124 ,"10"}; > 125 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 126 int rowCount = 1; > 127 int columnCount = 1; > 128 int _ = 1; > 129 END > 130 CASE(3) > 131 string A_[] = {"1110" > 132 ,"0001"}; > 133 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 134 int rowCount = 0; > 135 int columnCount = 0; > 136 int _ = 0; > 137 END > 138 CASE(4) > 139 string A_[] = {"01010101" > 140 ,"01010101" > 141 ,"01010101" > 142 ,"01010101" > 143 ,"01010101" > 144 ,"01010101" > 145 ,"01010101" > 146 ,"01010101"}; > 147 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 148 int rowCount = 2; > 149 int columnCount = 3; > 150 int _ = 8; > 151 END > 152 CASE(5) > 153 string A_[] = {"000000000000" > 154 ,"011101110111" > 155 ,"010001010101" > 156 ,"010001010101" > 157 ,"011101010101" > 158 ,"010101010101" > 159 ,"010101010101" > 160 ,"011101110111" > 161 ,"000000000000" > 162 ,"000000000000"}; > 163 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 164 int rowCount = 5; > 165 int columnCount = 9; > 166 int _ = 14; > 167 END > 168 CASE(6) > 169 string A_[] = {"11111101001110" > 170 ,"11000111111111" > 171 ,"00010101111001" > 172 ,"10110000111111" > 173 ,"10000011010010" > 174 ,"10001101101101" > 175 ,"00101010000001" > 176 ,"10111010100100" > 177 ,"11010011110111" > 178 ,"11100010110110" > 179 ,"00100101010100" > 180 ,"01001011001000" > 181 ,"01010001111010" > 182 ,"10100000010011"}; > 183 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 184 int rowCount = 6; > 185 int columnCount = 8; > 186 int _ = 31; > 187 END > 188 /* > 189 CASE(7) > 190 string A_[] = ; > 191 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 192 int rowCount = ; > 193 int columnCount = ; > 194 int _ = ; > 195 END > 196 CASE(8) > 197 string A_[] = ; > 198 vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 199 int rowCount = ; > 200 int columnCount = ; > 201 int _ = ; > 202 END > 203 */ > 204 } > 205 // END CUT HERE