Overview
| SHA1 Hash: | ddb24a372fa4bb8e57cd3f53b037bfdec52407e6 |
|---|---|
| Date: | 2012-10-19 16:27:06 |
| User: | kinaba |
| Comment: | 558 |
| 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/558-U/1A.cpp version [c9dd78f697e51c5a]
> 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 Stamp { public: > 23 int getMinimumCost(string desiredColor, int stampCost, int pushCost) > 24 { > 25 const int N = desiredColor.size(); > 26 > 27 int best = 0x7fffffff; > 28 for(int L=1; L<=N; ++L) { > 29 vector<int> dp(N+1, 999); > 30 dp[0] = 0; > 31 for(int e=1; e<=N; ++e) { > 32 set<char> colors; > 33 for(int s=e-1; s>=0; --s) { > 34 if(desiredColor[s] != '*') > 35 colors.insert(desiredColor[s]); > 36 if(colors.size()<=1 && e-s>=L) { > 37 int nPush = (e-s+L-1)/L; > 38 dp[e] = min(dp[e], dp[s]+nPush); > 39 } > 40 } > 41 } > 42 best = min(best, L*stampCost + dp[N]*pushCost); > 43 } > 44 return best; > 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 int& Expected, const int& 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(_, Stamp().getMinimumCost(desiredColor, stampCost, > 62 int main(){ > 63 > 64 CASE(0) > 65 string desiredColor = "RRGGBB"; > 66 int stampCost = 1; > 67 int pushCost = 1; > 68 int _ = 5; > 69 END > 70 CASE(1) > 71 string desiredColor = "R**GB*"; > 72 int stampCost = 1; > 73 int pushCost = 1; > 74 int _ = 5; > 75 END > 76 CASE(2) > 77 string desiredColor = "BRRB"; > 78 int stampCost = 2; > 79 int pushCost = 7; > 80 int _ = 30; > 81 END > 82 CASE(3) > 83 string desiredColor = "R*RR*GG"; > 84 int stampCost = 10; > 85 int pushCost = 58; > 86 int _ = 204; > 87 END > 88 CASE(4) > 89 string desiredColor = "*B**B**B*BB*G*BBB**B**B*"; > 90 int stampCost = 5; > 91 int pushCost = 2; > 92 int _ = 33; > 93 END > 94 CASE(5) > 95 string desiredColor = "*R*RG*G*GR*RGG*G*GGR***RR*GG"; > 96 int stampCost = 7; > 97 int pushCost = 1; > 98 int _ = 30; > 99 END > 100 /* > 101 CASE(6) > 102 string desiredColor = ; > 103 int stampCost = ; > 104 int pushCost = ; > 105 int _ = ; > 106 END > 107 CASE(7) > 108 string desiredColor = ; > 109 int stampCost = ; > 110 int pushCost = ; > 111 int _ = ; > 112 END > 113 */ > 114 } > 115 // END CUT HERE
Added SRM/558-U/1B.cpp version [a5fd0a0c4f174a5f]
> 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 Ear { public: > 23 long long getCount(vector <string> redX, vector <string> blueX, vector < > 24 { > 25 vector<int> rx, bx, by; > 26 { > 27 stringstream sin(accumulate(redX.begin(), redX.end(), st > 28 for(int x; sin>>x; ) rx.push_back(x); > 29 } > 30 { > 31 stringstream sin(accumulate(blueX.begin(), blueX.end(), > 32 for(int x; sin>>x; ) bx.push_back(x); > 33 } > 34 { > 35 stringstream sin(accumulate(blueY.begin(), blueY.end(), > 36 for(int y; sin>>y; ) by.push_back(y); > 37 } > 38 int B = bx.size(); > 39 > 40 LL total = 0; > 41 for(int p=0; p<B; ++p) > 42 for(int q=0; q<B; ++q) > 43 if(by[p] > by[q]) > 44 { > 45 int px=bx[p], py=by[p], qx=bx[q], qy=by[q]; > 46 LL a=0, b=0, c=0, d=0; > 47 for(int i=0; i<rx.size(); ++i) > 48 { > 49 int x = rx[i]; > 50 double z = px + (qx-px)*py/double(py-qy); > 51 if(x<min<double>(z,px)) > 52 ++a; > 53 if(min<double>(z,px)<=x && x<qx) > 54 ++b; > 55 if(qx<x && x<=max<double>(z,px)) > 56 ++c; > 57 if(max<double>(z,px)<x) > 58 ++d; > 59 } > 60 total += (a*(a-1)/2+a*b) * (d*(d-1)/2+d*c); > 61 } > 62 return total; > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const long long& Expected, const long long& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, Ear().getCount(redX, blueX, blueY));} > 80 int main(){ > 81 > 82 CASE(0) > 83 string redX_[] = {"3 2 8 7"}; > 84 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 85 string blueX_[] = {"5 4"}; > 86 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 87 string blueY_[] = {"2 4"}; > 88 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 89 long long _ = 1LL; > 90 END > 91 CASE(1) > 92 string redX_[] = {"3 2 8 7"}; > 93 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 94 string blueX_[] = {"2 8"}; > 95 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 96 string blueY_[] = {"3 4"}; > 97 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 98 long long _ = 0LL; > 99 END > 100 CASE(2) > 101 string redX_[] = {"1 2 6 9"}; > 102 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 103 string blueX_[] = {"3 6 8 5"}; > 104 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 105 string blueY_[] = {"1 5 4 3"}; > 106 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 107 long long _ = 4LL; > 108 END > 109 CASE(3) > 110 string redX_[] = {"10000"}; > 111 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 112 string blueX_[] = {"10000 9999"}; > 113 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 114 string blueY_[] = {"10000 9999"}; > 115 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 116 long long _ = 0LL; > 117 END > 118 CASE(4) > 119 string redX_[] = {"100 2", "00", " 39", "9", " 800 900 9", "99"}; > 120 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 121 string blueX_[] = {"15", "0 250 ", "349"}; > 122 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 123 string blueY_[] = {"2 3 1"}; > 124 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 125 long long _ = 12LL; > 126 END > 127 CASE(5) > 128 string redX_[] = {"1", " ", "2", " ", "3", " ", "4 5 6", " 7 8 9"}; > 129 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 130 string blueX_[] = {"4", " ", "5", " ", "6", " 7 ", "8"}; > 131 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 132 string blueY_[] = {"1", " 2 ", "3 4", " 5"}; > 133 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 134 long long _ = 204LL; > 135 END > 136 /* > 137 CASE(6) > 138 string redX_[] = ; > 139 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 140 string blueX_[] = ; > 141 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 142 string blueY_[] = ; > 143 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 144 long long _ = LL; > 145 END > 146 CASE(7) > 147 string redX_[] = ; > 148 vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); > 149 string blueX_[] = ; > 150 vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); > 151 string blueY_[] = ; > 152 vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); > 153 long long _ = LL; > 154 END > 155 */ > 156 } > 157 // END CUT HERE