Overview
| SHA1 Hash: | 7bc22ef7ab60a0d197e47d68a498f306355ef6c4 |
|---|---|
| Date: | 2013-04-12 00:57:05 |
| User: | kinaba |
| Comment: | 575 |
| 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/575-U/1A.cpp version [f9f0a181bc884140]
> 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 TheNumberGameDivOne { public: > 23 string find(long long n) > 24 { > 25 return solve(n) ? "John" : "Brus"; > 26 } > 27 > 28 bool solve(LL n) > 29 { > 30 if(n==1) > 31 return false; > 32 if( (n & (n-1)) == 0 ) > 33 { > 34 int k=0; > 35 for(; (1LL<<k)!=n; ++k) {} > 36 return k%2==0; > 37 } > 38 return n%2==0; > 39 } > 40 }; > 41 > 42 // BEGIN CUT HERE > 43 #include <ctime> > 44 double start_time; string timer() > 45 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 46 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 47 { os << "{ "; > 48 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 49 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 50 void verify_case(const string& Expected, const string& Received) { > 51 bool ok = (Expected == Received); > 52 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 53 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 54 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 55 #define END verify_case(_, TheNumberGameDivOne().find(n));} > 56 int main(){ > 57 > 58 CASE(0) > 59 long long n = 6LL; > 60 string _ = "John"; > 61 END > 62 CASE(1) > 63 long long n = 2LL; > 64 string _ = "Brus"; > 65 END > 66 CASE(2) > 67 long long n = 747LL; > 68 string _ = "Brus"; > 69 END > 70 CASE(3) > 71 long long n = 128LL; > 72 string _ = "Brus"; > 73 END > 74 CASE(4) > 75 long long n = 288230376151711744LL; > 76 string _ = "John"; > 77 END > 78 CASE(5) > 79 long long n = 1LL; > 80 string _ = "Brus"; > 81 END > 82 > 83 } > 84 // END CUT HERE
Added SRM/575-U/1B.cpp version [90d250afa9bcb948]
> 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 template<typename T> > 23 vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) > 24 { > 25 int N = a.size(); > 26 vector<T> u(N); > 27 for(int i=0; i<N; ++i) > 28 for(int j=0; j<N; ++j) > 29 u[i] += a[i][j]*v[j]; > 30 return u; > 31 } > 32 > 33 template<typename T> > 34 vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> > 35 { > 36 int N = a.size(); > 37 vector< vector<T> > c(N, vector<T>(N)); > 38 for(int i=0; i<N; ++i) > 39 for(int j=0; j<N; ++j) > 40 for(int k=0; k<N; ++k) > 41 c[i][j] += a[i][k]*b[k][j]; > 42 return c; > 43 } > 44 > 45 template<typename T> > 46 vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v) > 47 { > 48 for(; e; e>>=1, a=MATMUL(a,a)) > 49 if(e&1) > 50 v = MATMUL(a, v); > 51 return v; > 52 } > 53 > 54 class TheSwapsDivOne { public: > 55 double find(vector <string> sequence, int k) > 56 { > 57 const string S = accumulate(sequence.begin(), sequence.end(), st > 58 const int N = S.size(); > 59 > 60 // pos[p] = prob that position p is chosen. > 61 vector<double> pos(N); > 62 const double tot_range = (1+N)*N/2; > 63 for(int p=0; p<N; ++p) > 64 pos[p] = (p+1)*(N-p) / tot_range; > 65 double totpos = accumulate(pos.begin(), pos.end(), 0.0); > 66 > 67 double e = 0.0; > 68 > 69 double pStay = calc_stay(N, k); > 70 cerr<<pStay<<endl; > 71 for(int p=0; p<N; ++p) > 72 e += (S[p]-'0') * (pStay*pos[p] + (1-pStay)*(totpos-pos[ > 73 return e; > 74 } > 75 > 76 double calc_stay(int N, int k) > 77 { > 78 vector<double> v(2); > 79 v[0]=1, v[1]=0; > 80 > 81 vector<vector<double> > m(2, vector<double>(2)); > 82 double tot = N*(N-1)/2; > 83 m[0][0] = 1 - (N-1)/tot; > 84 m[0][1] = 1 - m[0][0]; > 85 m[1][0] = 1 / tot; > 86 m[1][1] = 1 - m[1][0]; > 87 > 88 v = MATPOWMUL(m, k, v); > 89 return v[0]; > 90 } > 91 }; > 92 > 93 // BEGIN CUT HERE > 94 #include <ctime> > 95 double start_time; string timer() > 96 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 97 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 98 { os << "{ "; > 99 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 100 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 101 void verify_case(const double& Expected, const double& Received) { > 102 bool ok = (abs(Expected - Received) < 1e-9); > 103 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 104 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 105 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 106 #define END verify_case(_, TheSwapsDivOne().find(sequence, k));} > 107 int main(){ > 108 > 109 CASE(0) > 110 string sequence_[] = {"4", "77"}; > 111 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 112 int k = 1; > 113 double _ = 10.0; > 114 END > 115 CASE(1) > 116 string sequence_[] = {"4", "77"}; > 117 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 118 int k = 47; > 119 double _ = 10.0; > 120 END > 121 CASE(2) > 122 string sequence_[] = {"1", "1", "1", "1", "1", "1", "1"}; > 123 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 124 int k = 1000000; > 125 double _ = 3.0; > 126 END > 127 CASE(3) > 128 string sequence_[] = {"572685085149095989026478064633266980348504469", " > 129 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 130 int k = 7; > 131 double _ = 98.3238536775161; > 132 END > 133 CASE(4) > 134 string sequence_[] = {"99119031434359106923816542810422135284590023481", > 135 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 136 int k = 1000000; > 137 double _ = -1.0; > 138 END > 139 CASE(5) > 140 string sequence_[] = {"71976811258237929702845263495922601783919868641", > 141 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 142 int k = 1000000; > 143 double _ = -1.0; > 144 END > 145 CASE(0) > 146 string sequence_[] = {"1", "2"}; > 147 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 148 int k = 1; > 149 double _ = 2.0; > 150 END > 151 CASE(0) > 152 string sequence_[] = {"1", "2"}; > 153 vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof > 154 int k = 2; > 155 double _ = 2.0; > 156 END > 157 > 158 } > 159 // END CUT HERE