Overview
| SHA1 Hash: | 744af0f22d95d2eea85eada0f51212d81d739310 |
|---|---|
| Date: | 2014-07-26 15:57:23 |
| User: | kinaba |
| Comment: | 628 |
| 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/628-U/1A.cpp version [e7ca75c1d92e9797]
> 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 DivisorsPower { public: > 23 long long findArgument(long long n) > 24 { > 25 LL cand = 1LL<<62; > 26 for(int p=2; p<=63; ++p) { > 27 LL xc = LL(pow(double(n), 1.0/p)); > 28 for(LL x=max(2LL,xc-100); x<=min(xc+100,n); ++x) > 29 if(ok(x,n)) > 30 cand = min(cand, x); > 31 } > 32 return (cand==(1LL<<62) ? -1 : cand); > 33 } > 34 > 35 int d(LL x) > 36 { > 37 int cnt = 1; > 38 for(int p=2; p*p<=x; ++p) > 39 if(x%p==0) { > 40 int k = 0; > 41 while(x%p==0) x/=p, ++k; > 42 cnt *= 1+k; > 43 } > 44 if(x>1) > 45 cnt *= 2; > 46 return cnt; > 47 } > 48 > 49 int ilog(LL x, LL n) > 50 { > 51 int cnt = 0; > 52 while(n%x==0) > 53 n/=x, ++cnt; > 54 return n>1 ? -1 : cnt; > 55 } > 56 > 57 > 58 bool ok(LL x, LL n) > 59 { > 60 return ilog(x, n) == d(x); > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const long long& Expected, const long long& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, DivisorsPower().findArgument(n));} > 78 int main(){ > 79 > 80 CASE(0) > 81 long long n = 4LL; > 82 long long _ = 2LL; > 83 END > 84 CASE(1) > 85 long long n = 10LL; > 86 long long _ = -1LL; > 87 END > 88 CASE(2) > 89 long long n = 64LL; > 90 long long _ = 4LL; > 91 END > 92 CASE(3) > 93 long long n = 10000LL; > 94 long long _ = 10LL; > 95 END > 96 CASE(4) > 97 long long n = 2498388559757689LL; > 98 long long _ = 49983883LL; > 99 END > 100 /* > 101 CASE(5) > 102 long long n = LL; > 103 long long _ = LL; > 104 END > 105 CASE(6) > 106 long long n = LL; > 107 long long _ = LL; > 108 END > 109 */ > 110 } > 111 // END CUT HERE
Added SRM/628-U/1B.cpp version [832763487ee7bc8f]
> 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 enum Type {X, SUM, MAX}; > 23 struct Tree { > 24 Type type; > 25 Tree* left; > 26 Tree* right; > 27 int size; > 28 ~Tree() { delete left; delete right; } > 29 }; > 30 > 31 class CircuitsConstruction { public: > 32 int maximizeResistance(string circuit, vector <int> conductors) > 33 { > 34 sort(conductors.rbegin(), conductors.rend()); > 35 const char* p = circuit.c_str(); > 36 Tree* t = parse(p); > 37 int ans = solve(t, conductors); > 38 delete t; > 39 return ans; > 40 } > 41 > 42 Tree* parse(const char*& p) > 43 { > 44 char tc = *p++; > 45 Tree* t = new Tree; > 46 t->type = (tc=='X' ? X : tc=='A' ? SUM : MAX); > 47 if(tc=='X') { > 48 t->left = t->right = 0; > 49 t->size = 1; > 50 } else { > 51 t->left = parse(p); > 52 t->right = parse(p); > 53 t->size = t->left->size + t->right->size; > 54 } > 55 return t; > 56 } > 57 > 58 int plusdepth(Tree* t) > 59 { > 60 switch(t->type) > 61 { > 62 case X: > 63 return 0; > 64 case SUM: > 65 return plusdepth(t->left) + plusdepth(t->right) + 1; > 66 case MAX: > 67 return max(plusdepth(t->left), plusdepth(t->right)); > 68 } > 69 } > 70 > 71 int solve(Tree* t, const vector<int>& c) > 72 { > 73 int n = plusdepth(t)+1; > 74 return accumulate(c.begin(), c.begin()+n, 0); > 75 } > 76 }; > 77 > 78 // BEGIN CUT HERE > 79 #include <ctime> > 80 double start_time; string timer() > 81 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 82 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 83 { os << "{ "; > 84 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 85 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 86 void verify_case(const int& Expected, const int& Received) { > 87 bool ok = (Expected == Received); > 88 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 89 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 90 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 91 #define END verify_case(_, CircuitsConstruction().maximizeResistance(circui > 92 int main(){ > 93 > 94 CASE(0) > 95 string circuit = "BXBXX"; > 96 int conductors_[] = {8, 2, 3}; > 97 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 98 int _ = 8; > 99 END > 100 CASE(1) > 101 string circuit = "AAXXAXAXX"; > 102 int conductors_[] = {1, 1, 2, 8, 10}; > 103 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 104 int _ = 22; > 105 END > 106 CASE(2) > 107 string circuit = "AXBXX"; > 108 int conductors_[] = {8, 2, 3}; > 109 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 110 int _ = 11; > 111 END > 112 CASE(3) > 113 string circuit = "BAAXBXXBXAXXBBAXXBXXAAXXX"; > 114 int conductors_[] = {17, 7, 21, 102, 56, 72, 88, 15, 9, 192, 16, 8, 30}; > 115 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 116 int _ = 454; > 117 END > 118 /* > 119 CASE(4) > 120 string circuit = ; > 121 int conductors_[] = ; > 122 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 123 int _ = ; > 124 END > 125 CASE(5) > 126 string circuit = ; > 127 int conductors_[] = ; > 128 vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/s > 129 int _ = ; > 130 END > 131 */ > 132 } > 133 // END CUT HERE
Added SRM/628-U/1C-U.cpp version [5d7fde43f099f38d]
> 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 DoraemonPuzzleGame { public: > 23 double solve(vector <int> X, vector <int> Y, int m) > 24 { > 25 int N = X.size(), M = m; > 26 vector<tuple<double,double,double>> P; > 27 for(int i=0; i<N; ++i) > 28 P.emplace_back( > 29 (1000-X[i]-Y[i])*0.001, > 30 X[i]*0.001, > 31 Y[i]*0.001 > 32 ); > 33 sort(P.begin(), P.end(), [&](const tuple<double,double,double>& > 34 if(get<2>(lhs) != get<2>(rhs)) return get<2>(lhs) > get< > 35 if(get<1>(lhs) != get<1>(rhs)) return get<1>(lhs) > get< > 36 return get<0>(lhs) > get<0>(rhs); > 37 }); > 38 return solve(M-N, P); > 39 } > 40 > 41 double solve(int Extra, const vector<tuple<double,double,double>>& P) > 42 { > 43 double eee = 0.0; > 44 for(int eff=0; eff<=P.size(); ++eff) > 45 { > 46 double e_clear = 0.0; > 47 vector<double> adv(1, 1.0); // adv[0] = 1.0; > 48 for(int i=0; i<P.size(); ++i) { > 49 double p1 = get<1>(P[i]); > 50 double p2 = get<2>(P[i]); > 51 if(i<eff) { > 52 e_clear += 1/p2; > 53 } else { > 54 double p = p1 + p2; > 55 e_clear += 1/p; > 56 > 57 vector<double> a2(adv.size()+1); > 58 for(int i=0; i<adv.size(); ++i) { > 59 a2[i] += adv[i] * p1/p; > 60 a2[i+1] += adv[i] * p2/p; > 61 } > 62 adv = a2; > 63 } > 64 } > 65 > 66 if(Extra <= eff) { > 67 best = min(best, e_clear); > 68 } else { > 69 best = min(best, > 70 } > 71 } > 72 return eee; > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const double& Expected, const double& Received) { > 85 bool ok = (abs(Expected - Received) < 1e-9); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, DoraemonPuzzleGame().solve(X, Y, m));} > 90 int main(){ > 91 > 92 CASE(0) > 93 int X_[] = {800}; > 94 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 95 int Y_[] = {200}; > 96 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 97 int m = 2; > 98 double _ = 5.0; > 99 END > 100 CASE(1) > 101 int X_[] = {1,999,999}; > 102 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 103 int Y_[] = {999,1,1}; > 104 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 105 int m = 3; > 106 double _ = 3.0; > 107 END > 108 CASE(2) > 109 int X_[] = {500,500}; > 110 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 111 int Y_[] = {500,500}; > 112 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 113 int m = 3; > 114 double _ = 2.5; > 115 END > 116 CASE(3) > 117 int X_[] = {250,250,250,250}; > 118 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 119 int Y_[] = {250,250,250,250}; > 120 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 121 int m = 5; > 122 double _ = 8.25; > 123 END > 124 CASE(4) > 125 int X_[] = {250,500,250}; > 126 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 127 int Y_[] = {500,250,500}; > 128 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 129 int m = 5; > 130 double _ = 4.962962962962963; > 131 END > 132 CASE(5) > 133 int X_[] = {600,900,800,500,900,200,400,100,800,300,900,300,800,700,800, > 134 800,700,600,900,600,300,100,300,100,700,500,900,200,800,400,300,700,300,400,700, > 135 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 136 int Y_[] = {400,100,200,500,100,800,600,900,200,700,100,700,200,300,200, > 137 200,300,400,100,400,700,900,700,900,300,500,100,800,200,600,700,300,700,600,300, > 138 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 139 int m = 95; > 140 double _ = 119.33578280666175; > 141 END > 142 /* > 143 CASE(6) > 144 int X_[] = ; > 145 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 146 int Y_[] = ; > 147 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 148 int m = ; > 149 double _ = ; > 150 END > 151 CASE(7) > 152 int X_[] = ; > 153 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 154 int Y_[] = ; > 155 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 156 int m = ; > 157 double _ = ; > 158 END > 159 */ > 160 } > 161 // END CUT HERE