Overview
| SHA1 Hash: | 4bef2b4eaf056d3c7ab10f01cc8d8a05fa05cd7b |
|---|---|
| Date: | 2011-04-10 07:55:59 |
| User: | kinaba |
| Comment: | 502 |
| 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/502-U/1A.cpp version [2978fcbee76e9eaf]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheLotteryBothDivs { public: > 23 double find(vector <string> goodSuffixes) > 24 { > 25 sort(goodSuffixes.begin(), goodSuffixes.end()); > 26 goodSuffixes.erase(unique(goodSuffixes.begin(), goodSuffixes.end > 27 double p = 0.0; > 28 for(int i=0; i<goodSuffixes.size(); ++i) { > 29 const string& me = goodSuffixes[i]; > 30 bool use = true; > 31 for(int k=0; k<goodSuffixes.size(); ++k) > 32 if( is_proper_suffix(me, goodSuffixes[k]) ) > 33 use = false; > 34 if( use ) > 35 p += pow(0.1, (double)me.size()); > 36 } > 37 return p; > 38 } > 39 bool is_proper_suffix(const string& me, const string& suf) > 40 { > 41 if( me.size() <= suf.size() ) > 42 return false; > 43 return me.substr(me.size()-suf.size()) == suf; > 44 } > 45 }; > 46 > 47 // BEGIN CUT HERE > 48 #include <ctime> > 49 double start_time; string timer() > 50 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 51 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 52 { os << "{ "; > 53 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 54 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 55 void verify_case(const double& Expected, const double& Received) { > 56 bool ok = (abs(Expected - Received) < 1e-9); > 57 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 58 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 59 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 60 #define END verify_case(_, TheLotteryBothDivs().find(goodSuffixes));} > 61 int main(){ > 62 > 63 CASE(0) > 64 string goodSuffixes_[] = {"4"}; > 65 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 66 double _ = 0.1; > 67 END > 68 CASE(1) > 69 string goodSuffixes_[] = {"4", "7"}; > 70 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 71 double _ = 0.2; > 72 END > 73 CASE(2) > 74 string goodSuffixes_[] = {"47", "47"}; > 75 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 76 double _ = 0.01; > 77 END > 78 CASE(3) > 79 string goodSuffixes_[] = {"47", "58", "4747", "502"}; > 80 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 81 double _ = 0.021; > 82 END > 83 CASE(4) > 84 string goodSuffixes_[] = {"8542861", "1954", "6", "523", "000000000", "5 > 85 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 86 double _ = 0.201100101; > 87 END > 88 /* > 89 CASE(5) > 90 string goodSuffixes_[] = ; > 91 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 92 double _ = ; > 93 END > 94 CASE(6) > 95 string goodSuffixes_[] = ; > 96 vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodS > 97 double _ = ; > 98 END > 99 */ > 100 } > 101 // END CUT HERE
Added SRM/502-U/1B-U.cpp version [4ee8e1b0161a0735]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class TheProgrammingContestDivOne { public: > 23 struct Problem > 24 { > 25 LL M; > 26 LL D; > 27 LL R; > 28 bool operator<(const Problem& rhs) const { > 29 if(R != rhs.R) return R < rhs.R; > 30 if(D != rhs.D) return D > rhs.D; > 31 return M > rhs.M; > 32 } > 33 }; > 34 int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, ve > 35 { > 36 const int N = maxPoints.size(); > 37 vector<Problem> ps; > 38 for(int i=0; i<N; ++i) { > 39 Problem p = {maxPoints[i], pointsPerMinute[i], requiredT > 40 ps.push_back(p); > 41 } > 42 sort(ps.begin(), ps.end()); > 43 > 44 LL best = 0; > 45 > 46 map<LL, LL> st; > 47 st[0] = 0; > 48 for(int i=0; i<N; ++i) > 49 { > 50 map<LL, LL> st2 = st; > 51 for(map<LL, LL>::iterator it=st.begin(); it!=st.end(); + > 52 { > 53 LL s = it->first; > 54 LL t = it->second; > 55 LL t2 = t + ps[i].R; > 56 if( t2 <= T ) { > 57 LL s2 = s + ps[i].M - ps[i].D * t2; > 58 best = max(best, s2); > 59 if( s2 > s ) { > 60 LL& entry = st2[s2]; > 61 if( entry==0 || entry>t2 ) > 62 entry = t2; > 63 } > 64 } > 65 } > 66 st.swap(st2); > 67 } > 68 return int(best); > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, TheProgrammingContestDivOne().find(T, maxPoints, > 86 int main(){ > 87 > 88 CASE(0) > 89 int T = 74; > 90 int maxPoints_[] = {502}; > 91 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 92 int pointsPerMinute_[] = {2}; > 93 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 94 int requiredTime_[] = {47}; > 95 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 96 int _ = 408; > 97 END > 98 CASE(1) > 99 int T = 40000; > 100 int maxPoints_[] = {100000, 100000}; > 101 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 102 int pointsPerMinute_[] = {1, 100000}; > 103 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 104 int requiredTime_[] = {50000, 30000}; > 105 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 106 int _ = 0; > 107 END > 108 CASE(2) > 109 int T = 75; > 110 int maxPoints_[] = {250, 500, 1000}; > 111 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 112 int pointsPerMinute_[] = {2, 4, 8}; > 113 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 114 int requiredTime_[] = {25, 25, 25}; > 115 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 116 int _ = 1200; > 117 END > 118 CASE(3) > 119 int T = 30; > 120 int maxPoints_[] = {100, 100, 100000}; > 121 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 122 int pointsPerMinute_[] = {1, 1, 100}; > 123 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 124 int requiredTime_[] = {15, 15, 30}; > 125 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 126 int _ = 97000; > 127 END > 128 CASE(4) > 129 int T = 100000; > 130 int maxPoints_[] = {100000,100000,100000,100000,100000,100000,100000,100 > 131 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 132 int pointsPerMinute_[] = {10,10,10,10,10,10,10,10,10,10,10,10,10,10,10 > 133 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 134 int requiredTime_[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192, > 135 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 136 int _ = -1; > 137 END > 138 CASE(5) > 139 int T = 100000; > 140 int maxPoints_[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,163 > 141 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 142 int pointsPerMinute_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 143 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 144 int requiredTime_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 > 145 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 146 int _ = -1; > 147 END > 148 /* > 149 CASE(5) > 150 int T = ; > 151 int maxPoints_[] = ; > 152 vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeo > 153 int pointsPerMinute_[] = ; > 154 vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof > 155 int requiredTime_[] = ; > 156 vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(required > 157 int _ = ; > 158 END > 159 */ > 160 } > 161 // END CUT HERE