Overview
| SHA1 Hash: | 535b5a8c1c33d82aefe4095ce4801e61c7c21554 |
|---|---|
| Date: | 2012-04-21 13:07:58 |
| User: | kinaba |
| Comment: | 540 |
| 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/540-U/1A.cpp version [b81dbf246dfff5e4]
> 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 ImportantSequence { public: > 29 int getCount(vector <int> B, string operators) > 30 { > 31 vector< pair<LL,LL> > A; > 32 A.push_back( make_pair(1,0) ); > 33 for(int i=0; i<B.size(); ++i) > 34 { > 35 LL a = A.back().first; > 36 LL b = A.back().second; > 37 LL c = B[i]; > 38 if( operators[i] == '+' ) { > 39 // (ax+b) + (px+q) = c > 40 A.push_back( make_pair(-a, c-b) ); > 41 } else { > 42 // (ax+b) - (px+q) = c > 43 A.push_back( make_pair(a, b-c) ); > 44 } > 45 } > 46 > 47 static const LL INF = (1LL<<62); > 48 LL xMin = 1; > 49 LL xMax = INF; > 50 for(int i=0; i<A.size(); ++i) > 51 { > 52 LL a = A[i].first; > 53 LL b = A[i].second; > 54 // ax + b > 0 > 55 if( a == +1 ) { > 56 // x > -b > 57 xMin = max(xMin, -b+1); > 58 } else { > 59 // -x > -b == x < b > 60 xMax = min(xMax, b-1); > 61 } > 62 } > 63 > 64 if( xMax == INF ) > 65 return -1; > 66 return (int)max(0LL, xMax-xMin+1); > 67 } > 68 }; > 69 > 70 // BEGIN CUT HERE > 71 #include <ctime> > 72 double start_time; string timer() > 73 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 74 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 75 { os << "{ "; > 76 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 77 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 78 void verify_case(const int& Expected, const int& Received) { > 79 bool ok = (Expected == Received); > 80 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 81 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 82 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 83 #define END verify_case(_, ImportantSequence().getCount(B, operators));} > 84 int main(){ > 85 > 86 CASE(0) > 87 int B_[] = {3, -1, 7}; > 88 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 89 string operators = "+-+"; > 90 int _ = 2; > 91 END > 92 CASE(1) > 93 int B_[] = {1}; > 94 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 95 string operators = "-"; > 96 int _ = -1; > 97 END > 98 CASE(2) > 99 int B_[] = {1}; > 100 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 101 string operators = "+"; > 102 int _ = 0; > 103 END > 104 CASE(3) > 105 int B_[] = {10}; > 106 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 107 string operators = "+"; > 108 int _ = 9; > 109 END > 110 CASE(4) > 111 int B_[] = {540, 2012, 540, 2012, 540, 2012, 540}; > 112 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 113 string operators = "-+-+-+-"; > 114 int _ = 1471; > 115 END > 116 CASE(5) > 117 int B_[] = {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, > 118 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, > 119 1000000000, 1000000000, 1000000000, 1000000000, > 120 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, > 121 1000000000, 1000000000, 1000000000, 1000000000, > 122 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, > 123 1000000000}; > 124 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 125 string operators = "------------------------------+"; > 126 int _ = -1; > 127 END > 128 /* > 129 CASE(6) > 130 int B_[] = ; > 131 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 132 string operators = ; > 133 int _ = ; > 134 END > 135 */ > 136 } > 137 // END CUT HERE
Added SRM/540-U/1B.cpp version [865c741d016d3d92]
> 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 RandomColoring { public: > 29 double getProbability(int N, int maxR, int maxG, int maxB, int startR, i > 30 { > 31 const int dx = d1-1; > 32 > 33 vector< vector< vector<double> > > p(maxR, vector<vector<double> > 34 p[startR][startG][startB] = 1.0; > 35 > 36 for(int i=1; i<N; ++i) > 37 { > 38 for(int r=0; r<maxR; ++r) > 39 for(int g=0; g<maxG; ++g) > 40 for(int b=0; b<maxB; ++b) { > 41 int c = cnt(maxR, maxG, maxB, r-d2, r+d2, g-d2, > 42 - (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, > 43 if( c ) > 44 p[r][g][b] /= c; > 45 else > 46 p[r][g][b] = 0; > 47 } > 48 > 49 vector< vector< vector<double> > > low = p; > 50 for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb) > 51 for(int r=0; r<maxR; ++r) > 52 for(int g=0; g<maxG; ++g) > 53 { > 54 int b = rgb-r-g; > 55 if( 0<=b && b<maxB ) { > 56 low[r][g][b] = > 57 p[r][g][b] > 58 + (r ? low[r-1][g][b] : 0) > 59 + (g ? low[r][g-1][b] : 0) > 60 + (b ? low[r][g][b-1] : 0) > 61 - (r&&g ? low[r-1][g-1][b] : 0) > 62 - (g&&b ? low[r][g-1][b-1] : 0) > 63 - (b&&r ? low[r-1][g][b-1] : 0) > 64 + (r&&g&&b ? low[r-1][g-1][b-1] > 65 } > 66 } > 67 > 68 vector< vector< vector<double> > > q = p; > 69 for(int r=0; r<maxR; ++r) > 70 for(int g=0; g<maxG; ++g) > 71 for(int b=0; b<maxB; ++b) > 72 { > 73 q[r][g][b] = > 74 zone(low, r-d2, r+d2, g-d2, g+d2, b-d2 > 75 - (d1==0 ? 0 : zone(low, r-dx, r+dx, g-d > 76 } > 77 p.swap(q); > 78 } > 79 > 80 vector< vector< vector<double> > > low = p; > 81 for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb) > 82 for(int r=0; r<maxR; ++r) > 83 for(int g=0; g<maxG; ++g) > 84 { > 85 int b = rgb-r-g; > 86 if( 0<=b && b<maxB ) { > 87 low[r][g][b] = > 88 p[r][g][b] > 89 + (r ? low[r-1][g][b] : 0) > 90 + (g ? low[r][g-1][b] : 0) > 91 + (b ? low[r][g][b-1] : 0) > 92 - (r&&g ? low[r-1][g-1][b] : 0) > 93 - (g&&b ? low[r][g-1][b-1] : 0) > 94 - (b&&r ? low[r-1][g][b-1] : 0) > 95 + (r&&g&&b ? low[r-1][g-1][b-1] : 0); > 96 } > 97 } > 98 > 99 return 1.0 - ( > 100 zone(low, startR-d2, startR+d2, startG-d2, startG+d2, st > 101 - (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx > 102 ); > 103 } > 104 > 105 double zone(const vector< vector< vector<double> > >& low, > 106 int r, int R, int g, int G, int b, int B) { > 107 r = max(0, min<int>(low.size()-1, r)); > 108 R = max(0, min<int>(low.size()-1, R)); > 109 g = max(0, min<int>(low[0].size()-1, g)); > 110 G = max(0, min<int>(low[0].size()-1, G)); > 111 b = max(0, min<int>(low[0][0].size()-1, b)); > 112 B = max(0, min<int>(low[0][0].size()-1, B)); > 113 return low[R][G][B] > 114 - (r ? low[r-1][G][B] : 0) > 115 - (g ? low[R][g-1][B] : 0) > 116 - (b ? low[R][G][b-1] : 0) > 117 + (r&&g ? low[r-1][g-1][B] : 0) > 118 + (g&&b ? low[R][g-1][b-1] : 0) > 119 + (b&&r ? low[r-1][G][b-1] : 0) > 120 - (r&&g&&b ? low[r-1][g-1][b-1] : 0); > 121 } > 122 > 123 int cnt(int maxR, int maxG, int maxB, > 124 int r, int R, int g, int G, int b, int B) { > 125 r = max(0, min<int>(maxR-1, r)); > 126 R = max(0, min<int>(maxR-1, R)); > 127 g = max(0, min<int>(maxG-1, g)); > 128 G = max(0, min<int>(maxG-1, G)); > 129 b = max(0, min<int>(maxB-1, b)); > 130 B = max(0, min<int>(maxB-1, B)); > 131 return (R-r+1)*(G-g+1)*(B-b+1); > 132 } > 133 }; > 134 > 135 // BEGIN CUT HERE > 136 #include <ctime> > 137 double start_time; string timer() > 138 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 139 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 140 { os << "{ "; > 141 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 142 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 143 void verify_case(const double& Expected, const double& Received) { > 144 bool ok = (abs(Expected - Received) < 1e-9); > 145 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 146 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 147 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 148 #define END verify_case(_, RandomColoring().getProbability(N, maxR, maxG, m > 149 int main(){ > 150 > 151 CASE(0) > 152 int N = 2; > 153 int maxR = 5; > 154 int maxG = 1; > 155 int maxB = 1; > 156 int startR = 2; > 157 int startG = 0; > 158 int startB = 0; > 159 int d1 = 0; > 160 int d2 = 1; > 161 double _ = 0.0; > 162 END > 163 CASE(1) > 164 int N = 3; > 165 int maxR = 5; > 166 int maxG = 1; > 167 int maxB = 1; > 168 int startR = 2; > 169 int startG = 0; > 170 int startB = 0; > 171 int d1 = 0; > 172 int d2 = 1; > 173 double _ = 0.22222222222222227; > 174 END > 175 CASE(2) > 176 int N = 7; > 177 int maxR = 4; > 178 int maxG = 2; > 179 int maxB = 2; > 180 int startR = 0; > 181 int startG = 0; > 182 int startB = 0; > 183 int d1 = 3; > 184 int d2 = 3; > 185 double _ = 1.0; > 186 END > 187 CASE(3) > 188 int N = 10; > 189 int maxR = 7; > 190 int maxG = 8; > 191 int maxB = 9; > 192 int startR = 1; > 193 int startG = 2; > 194 int startB = 3; > 195 int d1 = 0; > 196 int d2 = 10; > 197 double _ = 0.0; > 198 END > 199 CASE(4) > 200 int N = 10; > 201 int maxR = 7; > 202 int maxG = 8; > 203 int maxB = 9; > 204 int startR = 1; > 205 int startG = 2; > 206 int startB = 3; > 207 int d1 = 4; > 208 int d2 = 10; > 209 double _ = 0.37826245943967396; > 210 END > 211 CASE(5) > 212 int N = 3; > 213 int maxR = 3; > 214 int maxG = 2; > 215 int maxB = 2; > 216 int startR = 1; > 217 int startG = 0; > 218 int startB = 0; > 219 int d1 = 1; > 220 int d2 = 2; > 221 double _ = 0.09090909090909148; > 222 END > 223 /* > 224 CASE(6) > 225 int N = ; > 226 int maxR = ; > 227 int maxG = ; > 228 int maxB = ; > 229 int startR = ; > 230 int startG = ; > 231 int startB = ; > 232 int d1 = ; > 233 int d2 = ; > 234 double _ = ; > 235 END > 236 CASE(7) > 237 int N = ; > 238 int maxR = ; > 239 int maxG = ; > 240 int maxB = ; > 241 int startR = ; > 242 int startG = ; > 243 int startB = ; > 244 int d1 = ; > 245 int d2 = ; > 246 double _ = ; > 247 END > 248 */ > 249 } > 250 // END CUT HERE