Overview
| SHA1 Hash: | 2a8b395e2ee01d717cee6ebe5b8e45e23954d068 |
|---|---|
| Date: | 2012-03-07 11:07:44 |
| User: | kinaba |
| Comment: | 535 |
| 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/535-U/1A.cpp version [1549db04e8126d78]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 LL gcd(LL a, LL b) > 29 { > 30 while(a) > 31 swap(a, b%=a); > 32 return b; > 33 } > 34 > 35 class FoxAndGCDLCM { public: > 36 long long get(long long G, long long L) > 37 { > 38 if( L%G != 0 ) > 39 return -1; > 40 LL best = -1; > 41 LL z = L / G; > 42 for(LL p=1; p*p<=z; ++p) > 43 if( z%p==0 && gcd(p,z/p)==1 ) { > 44 LL A = G*p; > 45 LL B = G*(z/p); > 46 if( best == -1 || best > A+B ) > 47 best = A+B; > 48 } > 49 return best; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const long long& Expected, const long long& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, FoxAndGCDLCM().get(G, L));} > 67 int main(){ > 68 > 69 CASE(0) > 70 long long G = 2LL; > 71 long long L = 20LL; > 72 long long _ = 14LL; > 73 END > 74 CASE(1) > 75 long long G = 5LL; > 76 long long L = 8LL; > 77 long long _ = -1LL; > 78 END > 79 CASE(2) > 80 long long G = 1000LL; > 81 long long L = 100LL; > 82 long long _ = -1LL; > 83 END > 84 CASE(3) > 85 long long G = 100LL; > 86 long long L = 1000LL; > 87 long long _ = 700LL; > 88 END > 89 CASE(4) > 90 long long G = 10LL; > 91 long long L = 950863963000LL; > 92 long long _ = 6298430LL; > 93 END > 94 /* > 95 CASE(5) > 96 long long G = LL; > 97 long long L = LL; > 98 long long _ = LL; > 99 END > 100 CASE(6) > 101 long long G = LL; > 102 long long L = LL; > 103 long long _ = LL; > 104 END > 105 */ > 106 } > 107 // END CUT HERE
Added SRM/535-U/1B.cpp version [fecf6da132539bbe]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class FoxAndBusiness { public: > 29 double minimumCost(int K, int totalWork, vector <int> a, vector <int> p) > 30 { > 31 double L=0, R=1e+60; > 32 for(int _=0; _<10000; ++_) > 33 { > 34 double C = (L+R)/2; > 35 (possible(C, K, a, p) ? R : L) = C; > 36 } > 37 return R * totalWork; > 38 } > 39 > 40 bool possible(double C, int K, const vector<int>& a, const vector<int>& > 41 { > 42 vector<double> v; > 43 for(int i=0; i<a.size(); ++i) > 44 v.push_back( (C-p[i])*a[i] ); > 45 sort(v.rbegin(), v.rend()); > 46 double r = accumulate(v.begin(), v.begin()+K, 0.0); > 47 return 3600*double(K) <= r; > 48 } > 49 }; > 50 > 51 // BEGIN CUT HERE > 52 #include <ctime> > 53 double start_time; string timer() > 54 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 55 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 56 { os << "{ "; > 57 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 58 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 59 void verify_case(const double& Expected, const double& Received) { > 60 bool ok = (abs(Expected - Received) < 1e-9); > 61 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 62 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 63 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 64 #define END verify_case(_, FoxAndBusiness().minimumCost(K, totalWork, a, p) > 65 int main(){ > 66 > 67 CASE(0) > 68 int K = 1; > 69 int totalWork = 10; > 70 int a_[] = {10}; > 71 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 72 int p_[] = {20}; > 73 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 74 double _ = 3800.0; > 75 END > 76 CASE(1) > 77 int K = 1; > 78 int totalWork = 100; > 79 int a_[] = {50, 60}; > 80 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 81 int p_[] = {1000, 2000}; > 82 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 83 double _ = 107200.0; > 84 END > 85 CASE(2) > 86 int K = 2; > 87 int totalWork = 300; > 88 int a_[] = {10, 20, 47}; > 89 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 90 int p_[] = {15, 20, 98765}; > 91 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 92 double _ = 77500.0; > 93 END > 94 CASE(3) > 95 int K = 4; > 96 int totalWork = 1000; > 97 int a_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; > 98 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 99 int p_[] = {20, 30, 40, 58, 60, 70, 80, 90, 100, 150}; > 100 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 101 double _ = 531764.705882353; > 102 END > 103 CASE(4) > 104 int K = 25; > 105 int totalWork = 100000; > 106 int a_[] = {17016,47415,83045,39455,34491,97616,91719,95101,85384,68562, > 107 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 108 int p_[] = {59966,49102,35349,70206,65668,60145,10705,28056,9582,11619,8 > 109 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 110 double _ = -1; > 111 END > 112 CASE(5) > 113 int K = 1; > 114 int totalWork = 100000; > 115 int a_[] = {1}; > 116 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 117 int p_[] = {100000}; > 118 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 119 double _ = -1; > 120 END > 121 } > 122 // END CUT HERE