Overview
| SHA1 Hash: | 2e5fb9b56aa94910271e34ddda9efe99aaa02460 |
|---|---|
| Date: | 2013-02-13 09:35:23 |
| User: | kinaba |
| Comment: | 569 |
| 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/569-U/1A.cpp version [56f115457a162ea8]
> 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 TheDevice { public: > 23 int minimumAdditional(vector <string> plates) > 24 { > 25 int NB = plates[0].size(); > 26 int lackMax = 0; > 27 for(int i=0; i<NB; ++i) > 28 { > 29 int zero=0, one=0; > 30 for(int k=0; k<plates.size(); ++k) > 31 (plates[k][i]=='0' ? zero : one)++; > 32 int lack = max(0,1-zero)+max(0,2-one); > 33 lackMax = max(lackMax, lack); > 34 } > 35 return lackMax; > 36 } > 37 }; > 38 > 39 // BEGIN CUT HERE > 40 #include <ctime> > 41 double start_time; string timer() > 42 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 43 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 44 { os << "{ "; > 45 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 46 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 47 void verify_case(const int& Expected, const int& Received) { > 48 bool ok = (Expected == Received); > 49 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 50 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 51 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 52 #define END verify_case(_, TheDevice().minimumAdditional(plates));} > 53 int main(){ > 54 > 55 CASE(0) > 56 string plates_[] = {"010", > 57 "011", > 58 "101"}; > 59 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 60 int _ = 1; > 61 END > 62 CASE(1) > 63 string plates_[] = {"0", > 64 "1", > 65 "0", > 66 "1"}; > 67 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 68 int _ = 0; > 69 END > 70 CASE(2) > 71 string plates_[] = {"01010101", > 72 "10101010"}; > 73 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 74 int _ = 1; > 75 END > 76 CASE(3) > 77 string plates_[] = {"10010101011", > 78 "00010101001", > 79 "00100010111", > 80 "00101010101", > 81 "01010111101"}; > 82 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 83 int _ = 1; > 84 END > 85 CASE(4) > 86 string plates_[] = {"1101001011010", > 87 "0010000010101", > 88 "1010101011110", > 89 "1101010100111", > 90 "1011111110111"}; > 91 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 92 int _ = 0; > 93 END > 94 /* > 95 CASE(5) > 96 string plates_[] = ; > 97 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 98 int _ = ; > 99 END > 100 CASE(6) > 101 string plates_[] = ; > 102 vector <string> plates(plates_, plates_+sizeof(plates_)/sizeof(*plates > 103 int _ = ; > 104 END > 105 */ > 106 } > 107 // END CUT HERE
Added SRM/569-U/1B.cpp version [383a00a9f345cc0f]
> 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 TheJediTest { public: > 23 int minimumSupervisors(vector <int> students, int K) > 24 { > 25 return rec(0, 0, students, K); > 26 } > 27 > 28 int rec(int i, int dsi, const vector<int>& s, int K) > 29 { > 30 if(i+1 == s.size()) > 31 return (s[i]+dsi+K-1) / K; > 32 > 33 int maxMoveOut = (dsi<0 ? s[i]+dsi : s[i]); > 34 int maxMoveIn = s[i+1]; > 35 int X = s[i] + dsi; > 36 > 37 int best = 0x7fffffff; > 38 > 39 int Xout = X/K*K; > 40 if(X-Xout > maxMoveOut) > 41 Xout = X-maxMoveOut; > 42 best = min(best, (Xout+K-1)/K + rec(i+1, X-Xout, s, K)); > 43 > 44 int Xin = (X/K+1)*K; > 45 if(Xin-X > maxMoveIn) > 46 Xin = X+maxMoveIn; > 47 best = min(best, (Xin+K-1)/K + rec(i+1, X-Xin, s, K)); > 48 return best; > 49 } > 50 }; > 51 > 52 // BEGIN CUT HERE > 53 #include <ctime> > 54 double start_time; string timer() > 55 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 56 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 57 { os << "{ "; > 58 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 59 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 60 void verify_case(const int& Expected, const int& Received) { > 61 bool ok = (Expected == Received); > 62 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 63 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 64 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 65 #define END verify_case(_, TheJediTest().minimumSupervisors(students, K));} > 66 int main(){ > 67 > 68 CASE(0) > 69 int students_[] = {3, 6, 3}; > 70 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 71 int K = 4; > 72 int _ = 3; > 73 END > 74 CASE(1) > 75 int students_[] = {1, 1, 1, 1}; > 76 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 77 int K = 4; > 78 int _ = 2; > 79 END > 80 CASE(2) > 81 int students_[] = {0, 0, 0, 0}; > 82 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 83 int K = 12345; > 84 int _ = 0; > 85 END > 86 CASE(3) > 87 int students_[] = {15, 0, 13, 4, 29, 6, 2}; > 88 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 89 int K = 7; > 90 int _ = 10; > 91 END > 92 CASE(4) > 93 int students_[] = {1284912, 1009228, 9289247, 2157, 2518, 52781, 2, 2818 > 94 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 95 int K = 114; > 96 int _ = 102138; > 97 END > 98 CASE(5) > 99 int students_[] = {4,0,5}; > 100 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 101 int K = 3; > 102 int _ = 3; > 103 END > 104 /* > 105 CASE(6) > 106 int students_[] = ; > 107 vector <int> students(students_, students_+sizeof(students_)/sizeof(*s > 108 int K = ; > 109 int _ = ; > 110 END > 111 */ > 112 } > 113 // END CUT HERE