Overview
| SHA1 Hash: | 5b7cb6883da0a64bd2da0e229092f81925fcef86 |
|---|---|
| Date: | 2015-09-28 10:08:59 |
| User: | kinaba |
| Comment: | 667 |
| 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/667-U/1A-U.cpp version [8f81dce206d33d35]
> 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 inline int bitcnt(int x) > 23 { > 24 int c = 0; > 25 for(; x; x>>=1) > 26 c += x&1; > 27 return c; > 28 } > 29 > 30 class OrderOfOperations { public: > 31 int minTime(vector <string> s) > 32 { > 33 const int M = s[0].size(); > 34 > 35 vector<int> edge; > 36 int all = 0; > 37 for(auto& si: s) { > 38 int x = 0; > 39 for(int i=0; i<M; ++i) > 40 x |= (si[i]=='1')<<i; > 41 edge.emplace_back(x); > 42 all |= x; > 43 } > 44 vector<int> nbits; > 45 for(int m=0; m<(1<<M); ++m) > 46 nbits.emplace_back(bitcnt(m)); > 47 > 48 typedef int Vert, Cost; > 49 typedef pair<Cost,Vert> Edge; > 50 priority_queue<Edge, vector<Edge>, greater<Edge>> Q; > 51 Q.emplace(0, 0); > 52 vector<bool> V(1<<M); > 53 while(!Q.empty()) > 54 { > 55 Vert v = Q.top().second; > 56 Cost c = Q.top().first; > 57 Q.pop(); > 58 if( V[v] ) > 59 continue; > 60 V[v] = true; > 61 > 62 if( v == all ) > 63 return c; > 64 > 65 for(auto e: edge) > 66 if( !V[v|e] ) > 67 Q.emplace(c+nbits[(v|e)&~v]*nbits[(v|e)& > 68 } > 69 return -1; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const int& Expected, const int& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, OrderOfOperations().minTime(s));} > 87 int main(){ > 88 > 89 CASE(0) > 90 string s_[] = { > 91 "111", > 92 "001", > 93 "010" > 94 }; > 95 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 96 int _ = 3; > 97 END > 98 CASE(1) > 99 string s_[] = { > 100 "11101", > 101 "00111", > 102 "10101", > 103 "00000", > 104 "11000" > 105 }; > 106 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 107 int _ = 9; > 108 END > 109 CASE(2) > 110 string s_[] = { > 111 "11111111111111111111" > 112 }; > 113 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 114 int _ = 400; > 115 END > 116 CASE(3) > 117 string s_[] = { > 118 "1000", > 119 "1100", > 120 "1110" > 121 }; > 122 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 123 int _ = 3; > 124 END > 125 CASE(4) > 126 string s_[] = { > 127 "111", > 128 "111", > 129 "110", > 130 "100" > 131 }; > 132 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 133 int _ = 3; > 134 END > 135 CASE(5) > 136 string s_[] = {"00100001010101000101","11011001110001000111","0101100101 > 137 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 138 int _ = -2; > 139 END > 140 CASE(6) > 141 string s_[] = { > 142 "1100", > 143 "0011", > 144 "0110", > 145 }; > 146 vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 147 int _ = 6; > 148 END > 149 } > 150 // END CUT HERE
Added SRM/667-U/1B-U.cpp version [e7836058c4211ebe]
> 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 CatsOnTheCircle { public: > 23 int N; > 24 double p; > 25 > 26 double getProb(int N_, int K, int p_) > 27 { > 28 N = N_; > 29 p = p_ / pow(10.0,9); > 30 return rec(false, 1, K-1); > 31 } > 32 /* > 33 void rec2(int V, > 34 vector<double>* p_t2e, > 35 vector<double>* q_t2e) { > 36 if(V == N-1) { > 37 p_t2e->assign(1, 1.0); > 38 q_t2e->assign(1, 1.0); > 39 return; > 40 } > 41 > 42 vector<double> pp, qq; > 43 rec2(V+1, &pp, &qq); > 44 > 45 vector<double> pp2; > 46 pp2 += (pp<<1) * rightOut(p,V); > 47 pp2 += rev(qq<<1) * (1-rightOut(p,V)); > 48 } > 49 */ > 50 double rec(bool inv, int V, int T) { > 51 if(V == N-1) > 52 return 1.0; > 53 double pp = 0.0; > 54 if(T!=0) pp += rightOut(inv?1-p:p,V) * rec(inv, V+1,T-1); > 55 if(T!=N-V-1) pp += (1-rightOut(inv?1-p:p,V)) * rec(!inv, V+1,N-V > 56 return pp; > 57 } > 58 > 59 double rightOut(const double p, int V) { > 60 if(V==1) > 61 return p; > 62 //x = p + (1-p)y > 63 //y = rightOut(V-1)x > 64 return p / (1 - (1-p)*rightOut(p, V-1)); > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const double& Expected, const double& Received) { > 77 bool ok = (abs(Expected - Received) < 1e-9); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, CatsOnTheCircle().getProb(N, K, p));} > 82 int main(){ > 83 > 84 CASE(0) > 85 int N = 3; > 86 int K = 1; > 87 int p = 300000000; > 88 double _ = 0.6999999999999985; > 89 END > 90 CASE(1) > 91 int N = 6; > 92 int K = 2; > 93 int p = 500000000; > 94 double _ = 0.2; > 95 END > 96 CASE(2) > 97 int N = 6; > 98 int K = 5; > 99 int p = 500000000; > 100 double _ = 0.2; > 101 END > 102 CASE(3) > 103 int N = 10; > 104 int K = 2; > 105 int p = 666666666; > 106 double _ = 0.00391389439551009; > 107 END > 108 CASE(4) > 109 int N = 999999999; > 110 int K = 999999996; > 111 int p = 777777777; > 112 double _ = 0.05830903870125612; > 113 END > 114 CASE(5) > 115 int N = 1000000000; > 116 int K = 4; > 117 int p = 300000000; > 118 double _ = 0.044981259448371; > 119 END > 120 CASE(6) > 121 int N = 534428790; > 122 int K = 459947197; > 123 int p = 500000000; > 124 double _ = 1.871156682766205E-9; > 125 END > 126 /* > 127 CASE(7) > 128 int N = ; > 129 int K = ; > 130 int p = ; > 131 double _ = ; > 132 END > 133 CASE(8) > 134 int N = ; > 135 int K = ; > 136 int p = ; > 137 double _ = ; > 138 END > 139 */ > 140 } > 141 // END CUT HERE