Overview
| SHA1 Hash: | 0bad7aa88714bbcd922282ab43c15e88b24ffdbb |
|---|---|
| Date: | 2013-12-14 05:06:43 |
| User: | kinaba |
| Comment: | 599 |
| 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/599-U/1A.cpp version [acca555346b2264d]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BigFatInteger { public: > 23 int minOperations(int A, int B) > 24 { > 25 vector<int> s; > 26 for(int p=2; p*p<=A; ++p) > 27 { > 28 int c = 0; > 29 while(A%p==0) A/=p, ++c; > 30 if(c) s.push_back(c*B); > 31 } > 32 if(A>1) > 33 s.push_back(1*B); > 34 > 35 int cnt = s.size(); > 36 vector<int> cur(s.size(), 1); > 37 while(cur != s) > 38 { > 39 for(int i=0; i<s.size(); ++i) > 40 cur[i] = min(cur[i]*2, s[i]); > 41 ++cnt; > 42 } > 43 return cnt; > 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 int& Expected, const int& Received) { > 56 bool ok = (Expected == Received); > 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(_, BigFatInteger().minOperations(A, B));} > 61 int main(){ > 62 > 63 CASE(0) > 64 int A = 6; > 65 int B = 1; > 66 int _ = 2; > 67 END > 68 CASE(1) > 69 int A = 162; > 70 int B = 1; > 71 int _ = 4; > 72 END > 73 CASE(2) > 74 int A = 999983; > 75 int B = 9; > 76 int _ = 5; > 77 END > 78 CASE(3) > 79 int A = 360; > 80 int B = 8; > 81 int _ = 8; > 82 END > 83 CASE(4) > 84 int A = 1000000; > 85 int B = 1000000; > 86 int _ = -1; > 87 END > 88 CASE(5) > 89 int A = 2*3*5*7*11*13*17; > 90 int B = 1000000; > 91 int _ = -1; > 92 END > 93 > 94 } > 95 // END CUT HERE
Added SRM/599-U/1B.cpp version [18e652cfb8226cd8]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 int gcd(int a, int b) > 23 { > 24 while(a) > 25 swap(a, b%=a); > 26 return b; > 27 } > 28 > 29 class FindPolygons { public: > 30 double minimumPolygon(int L) > 31 { > 32 if(L<=2) > 33 return -1; > 34 if(L%2==1) // euclid%2 == manhattan%2. tour is always even. > 35 return -1; > 36 > 37 map<int, vector<pair<int,int>>> pyt; > 38 for(int k=1; k<=L; ++k) { > 39 auto& pk = pyt[k]; > 40 pk.emplace_back(0, k); > 41 pk.emplace_back(k, 0); > 42 pk.emplace_back(0, -k); > 43 pk.emplace_back(-k, 0); > 44 } > 45 for(int m=1; m*m<=L/2; ++m) > 46 for(int n=1; n<m && m*m+n*n<=L/2; ++n) > 47 if(((m^n)&1) && gcd(m,n)==1) { > 48 int a = m*m-n*n, b = 2*m*n, c = m*m+n*n; > 49 for(int k=1; k*c<=L; ++k) { > 50 auto& pk = pyt[k*c]; > 51 pk.emplace_back(k*a, k*b); > 52 pk.emplace_back(k*a, -k*b); > 53 pk.emplace_back(-k*a, k*b); > 54 pk.emplace_back(-k*a, -k*b); > 55 pk.emplace_back(k*b, k*a); > 56 pk.emplace_back(k*b, -k*a); > 57 pk.emplace_back(-k*b, k*a); > 58 pk.emplace_back(-k*b, -k*a); > 59 } > 60 } > 61 > 62 // Triangle > 63 int best = L; > 64 for(int a=1; a*3<=L; ++a) > 65 for(int b=a; a+b*2<=L; ++b) > 66 { > 67 int c = L-a-b; > 68 > 69 for(auto& av : pyt[a]) > 70 { > 71 int ax=av.first; > 72 int ay=av.second; > 73 if(ax>=0 && ay>=0) > 74 for(auto& bv : pyt[b]) > 75 { > 76 int bx=bv.first; > 77 int by=bv.second; > 78 int cx=-ax-bx; > 79 int cy=-ay-by; > 80 if(ax*by!=ay*bx && cx*cx+cy*cy = > 81 best = min(best, c-a); > 82 break; > 83 } > 84 } > 85 } > 86 } > 87 if(best < L) > 88 return best; > 89 // Rectangle > 90 if(L%4==0) > 91 return 0; > 92 return 1; > 93 } > 94 }; > 95 > 96 // BEGIN CUT HERE > 97 #include <ctime> > 98 double start_time; string timer() > 99 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 100 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 101 { os << "{ "; > 102 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 103 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 104 void verify_case(const double& Expected, const double& Received) { > 105 bool ok = (abs(Expected - Received) < 1e-9); > 106 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 107 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 108 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 109 #define END verify_case(_, FindPolygons().minimumPolygon(L));} > 110 int main(){ > 111 CASE(0) > 112 int L = 4; > 113 double _ = 0.0; > 114 END > 115 CASE(1) > 116 int L = 5; > 117 double _ = -1.0; > 118 END > 119 CASE(2) > 120 int L = 12; > 121 double _ = 2.0; > 122 END > 123 CASE(3) > 124 int L = 4984; > 125 double _ = 819.0; > 126 END > 127 CASE(4) > 128 int L = 5000; > 129 double _ = -999; > 130 END > 131 CASE(4) > 132 int L = 20; > 133 double _ = -999; > 134 END > 135 /* > 136 CASE(5) > 137 int L = ; > 138 double _ = ; > 139 END > 140 */ > 141 } > 142 // END CUT HERE