Overview
| SHA1 Hash: | f7e7bde312d502a7dcc4d3f39a16b65515555f8a |
|---|---|
| Date: | 2012-09-01 14:42:22 |
| User: | kinaba |
| Comment: | Practice. |
| 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/553-U/1A.cpp version [ede2eda09095edba]
> 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 Suminator { public: > 23 int findMissing(vector <int> program, int wantedResult) > 24 { > 25 set<int> cand; > 26 > 27 int it = find(program.begin(), program.end(), -1) - program.begi > 28 program[it] = 0; > 29 if( eval(program) == complex<LL>(wantedResult, 0) ) > 30 cand.insert(0); > 31 program[it] = -1; > 32 > 33 complex<LL> r = eval(program); > 34 if( r.imag()==0 ) { > 35 if( r.real()==wantedResult ) > 36 cand.insert(1); > 37 } else { > 38 // r.real() + r.imag()*modify == wantedResult > 39 if( wantedResult > r.real() ) > 40 if( (wantedResult - r.real()) % r.imag() == 0 ) > 41 cand.insert(int((wantedResult - r.real() > 42 } > 43 > 44 return cand.empty() ? -1 : *cand.begin(); > 45 } > 46 > 47 complex<LL> eval(const vector<int>& p) > 48 { > 49 stack< complex<LL> > stk; > 50 for(int i=0; i<p.size(); ++i) > 51 if(p[i] == -1) > 52 stk.push(complex<LL>(0,1)); > 53 else if(p[i] != 0) > 54 stk.push(complex<LL>(p[i],0)); > 55 else { > 56 complex<LL> a = 0; if(!stk.empty()){ a=stk.top() > 57 complex<LL> b = 0; if(!stk.empty()){ b=stk.top() > 58 stk.push(a+b); > 59 } > 60 complex<LL> r = 0; if(!stk.empty()){ r=stk.top(); stk.pop(); } > 61 return r; > 62 } > 63 }; > 64 > 65 // BEGIN CUT HERE > 66 #include <ctime> > 67 double start_time; string timer() > 68 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 69 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 70 { os << "{ "; > 71 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 72 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 73 void verify_case(const int& Expected, const int& Received) { > 74 bool ok = (Expected == Received); > 75 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 76 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 77 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 78 #define END verify_case(_, Suminator().findMissing(program, wantedResult)); > 79 int main(){ > 80 > 81 CASE(0) > 82 int program_[] = {7,-1,0}; > 83 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 84 int wantedResult = 10; > 85 int _ = 3; > 86 END > 87 CASE(1) > 88 int program_[] = {100, 200, 300, 0, 100, -1}; > 89 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 90 int wantedResult = 600; > 91 int _ = 0; > 92 END > 93 CASE(2) > 94 int program_[] = {-1, 7, 3, 0, 1, 2, 0, 0}; > 95 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 96 int wantedResult = 13; > 97 int _ = 0; > 98 END > 99 CASE(3) > 100 int program_[] = {-1, 8, 4, 0, 1, 2, 0, 0}; > 101 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 102 int wantedResult = 16; > 103 int _ = -1; > 104 END > 105 CASE(4) > 106 int program_[] = {1000000000, 1000000000, 1000000000, 1000000000, -1, 0 > 107 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 108 int wantedResult = 1000000000; > 109 int _ = -1; > 110 END > 111 CASE(5) > 112 int program_[] = {7, -1, 3, 0}; > 113 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 114 int wantedResult = 3; > 115 int _ = -1; > 116 END > 117 /* > 118 CASE(6) > 119 int program_[] = ; > 120 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 121 int wantedResult = ; > 122 int _ = ; > 123 END > 124 CASE(7) > 125 int program_[] = ; > 126 vector <int> program(program_, program_+sizeof(program_)/sizeof(*progr > 127 int wantedResult = ; > 128 int _ = ; > 129 END > 130 */ > 131 } > 132 // END CUT HERE
Added SRM/553-U/2A.cpp version [438fa969580e8113]
> 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 PlatypusDuckAndBeaver { public: > 23 int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) > 24 { > 25 // 2 1 0 > 26 // 4 0 1 > 27 // 4 1 1 > 28 for(int c=0 ;; ++c) > 29 { > 30 int a = duckBills - c; > 31 int b = beaverTails - c; > 32 if(a*2+b*4+c*4 == webbedFeet) > 33 return a+b+c; > 34 } > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const int& Expected, const int& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, PlatypusDuckAndBeaver().minimumAnimals(webbedFee > 52 int main(){ > 53 > 54 CASE(0) > 55 int webbedFeet = 4; > 56 int duckBills = 1; > 57 int beaverTails = 1; > 58 int _ = 1; > 59 END > 60 CASE(1) > 61 int webbedFeet = 0; > 62 int duckBills = 0; > 63 int beaverTails = 0; > 64 int _ = 0; > 65 END > 66 CASE(2) > 67 int webbedFeet = 10; > 68 int duckBills = 2; > 69 int beaverTails = 2; > 70 int _ = 3; > 71 END > 72 CASE(3) > 73 int webbedFeet = 60; > 74 int duckBills = 10; > 75 int beaverTails = 10; > 76 int _ = 20; > 77 END > 78 CASE(4) > 79 int webbedFeet = 1000; > 80 int duckBills = 200; > 81 int beaverTails = 200; > 82 int _ = 300; > 83 END > 84 /* > 85 CASE(5) > 86 int webbedFeet = ; > 87 int duckBills = ; > 88 int beaverTails = ; > 89 int _ = ; > 90 END > 91 CASE(6) > 92 int webbedFeet = ; > 93 int duckBills = ; > 94 int beaverTails = ; > 95 int _ = ; > 96 END > 97 */ > 98 } > 99 // END CUT HERE
Added SRM/553-U/2C.cpp version [1cbd37b2af1920c6]
> 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 SafeRemoval { public: > 23 int removeThem(vector <int> seq, int K) > 24 { > 25 sort(seq.begin(), seq.end()); > 26 const int sum = accumulate(seq.begin(), seq.end(), 0); > 27 > 28 vector<int> cls[4]; > 29 for(int i=0; i<seq.size(); ++i) > 30 cls[seq[i]%4].push_back(seq[i]); > 31 > 32 int best = -1; > 33 for(int r=0; r<4; ++r) { > 34 int b = rec(cls, 0, 0, 0, 0, K, sum%4); > 35 if(b != -1) > 36 best = max(best, sum-b); > 37 } > 38 return best; > 39 } > 40 > 41 map<int, int> memo; > 42 int rec(const vector<int> cls[4], int a, int b, int c, int d, int K, int > 43 { > 44 if(K==0) > 45 return (R==0 ? -1 : 0); > 46 const int key = ((((K*51+a)*51+b)*51+c)*51+d)*4+R; > 47 if(memo.count(key)) > 48 return memo[key]; > 49 > 50 int i[4] = {a,b,c,d}; > 51 int best = -1; > 52 for(int k=0; k<4; ++k) if(R!=k && i[k]<cls[k].size()) { > 53 i[k]++; > 54 int b = rec(cls, i[0], i[1], i[2], i[3], K-1, (R-k+4)%4) > 55 i[k]--; > 56 if(b != -1) { > 57 b += cls[k][i[k]]; > 58 best = (best==-1 ? b : min(best, b)); > 59 } > 60 } > 61 return memo[key] = best; > 62 } > 63 }; > 64 > 65 // BEGIN CUT HERE > 66 #include <ctime> > 67 double start_time; string timer() > 68 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 69 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 70 { os << "{ "; > 71 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 72 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 73 void verify_case(const int& Expected, const int& Received) { > 74 bool ok = (Expected == Received); > 75 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 76 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 77 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 78 #define END verify_case(_, SafeRemoval().removeThem(seq, k));} > 79 int main(){ > 80 > 81 CASE(0) > 82 int seq_[] = {3, 8, 4}; > 83 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 84 int k = 1; > 85 int _ = 11; > 86 END > 87 CASE(1) > 88 int seq_[] = {1,1,1,1,1,1}; > 89 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 90 int k = 3; > 91 int _ = -1; > 92 END > 93 CASE(2) > 94 int seq_[] = {1,6,1,10,1,2,7,11}; > 95 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 96 int k = 6; > 97 int _ = 21; > 98 END > 99 CASE(3) > 100 int seq_[] = {1,1,1,1,1,1,1,1,7}; > 101 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 102 int k = 3; > 103 int _ = 6; > 104 END > 105 /* > 106 CASE(4) > 107 int seq_[] = ; > 108 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 109 int k = ; > 110 int _ = ; > 111 END > 112 CASE(5) > 113 int seq_[] = ; > 114 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 115 int k = ; > 116 int _ = ; > 117 END > 118 */ > 119 } > 120 // END CUT HERE