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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 81 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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, 1000000000, 120 + 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 121 + 1000000000, 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, int startG, int startB, int d1, int d2) 30 + { 31 + const int dx = d1-1; 32 + 33 + vector< vector< vector<double> > > p(maxR, vector<vector<double> >(maxG, vector<double>(maxB))); 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, g+d2, b-d2, b+d2) 42 + - (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, g-dx, g+dx, b-dx, b+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] : 0); 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, b+d2) 75 + - (d1==0 ? 0 : zone(low, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx)); 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, startB-d2, startB+d2) 101 + - (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx, startG+dx, startB-dx, startB+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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 146 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 147 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 148 +#define END verify_case(_, RandomColoring().getProbability(N, maxR, maxG, maxB, startR, startG, startB, d1, d2));} 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