Overview
| SHA1 Hash: | ba35b3a9cf1201e875336ba54dc7417160616956 |
|---|---|
| Date: | 2011-06-25 15:38:24 |
| User: | kinaba |
| Comment: | 510 |
| 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/510-U/1A.cpp version [4b8ef53b93c8e743]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class TheAlmostLuckyNumbersDivOne { public: 23 + LL rec(LL n, int miss_atmost=1, LL prefix=0) 24 + { 25 + if( n<prefix || miss_atmost<0 ) 26 + return 0; 27 + LL cnt = (prefix==0?0:1); 28 + for(int i=(prefix==0?1:0); i<=9; ++i) 29 + cnt += rec(n, miss_atmost-(i==4||i==7?0:1), prefix*10+i); 30 + return cnt; 31 + } 32 + LL find(LL a, LL b) 33 + { 34 + return rec(b) - rec(a-1); 35 + LL cnt = 0; 36 + for(int len=1; len<=16; ++len) // 長さ len の 37 + for(int pat=0; pat<(1<<len); ++pat) // ビットパターンを全列挙 38 + { 39 + // [0,1] -> [4,7] に変えれば lucky number の全生成 40 + LL val = 0; 41 + for(int i=0; i<len; ++i) 42 + val = val*10 + (pat&(1<<i) ? 7 : 4); 43 + if( a<=val && val<=b ) 44 + ++cnt; 45 + 46 + // Almost Lucky Number は 1 箇所違う 47 + for(int m=0; m<len; ++m) if(pat&(1<<m)) // 7 を変えて 48 + for(int mTo=(m==0?1:0); mTo<=9; ++mTo) if(mTo!=4 && mTo!=7) // 0-3,5-6,8-9 にしてみる 49 + { 50 + LL val = 0; 51 + for(int i=0; i<len; ++i) 52 + val = val*10 + (i==m ? mTo : (pat&(1<<i)) ? 7 : 4); 53 + if( a<=val && val<=b ) 54 + ++cnt; 55 + } 56 + } 57 + return cnt; 58 + } 59 +}; 60 + 61 +// BEGIN CUT HERE 62 +#include <ctime> 63 +double start_time; string timer() 64 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 65 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 66 + { os << "{ "; 67 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 68 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 69 +void verify_case(const long long& Expected, const long long& Received) { 70 + bool ok = (Expected == Received); 71 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 72 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 73 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 74 +#define END verify_case(_, TheAlmostLuckyNumbersDivOne().find(a, b));} 75 +int main(){ 76 + 77 +CASE(0) 78 + long long a = 4LL; 79 + long long b = 7LL; 80 + long long _ = 4LL; 81 +END 82 +CASE(1) 83 + long long a = 8LL; 84 + long long b = 19LL; 85 + long long _ = 4LL; 86 +END 87 +CASE(2) 88 + long long a = 28LL; 89 + long long b = 33LL; 90 + long long _ = 0LL; 91 +END 92 +CASE(3) 93 + long long a = 12345678900LL; 94 + long long b = 98765432100LL; 95 + long long _ = 91136LL; 96 +END 97 +CASE(4) 98 + long long a = 1LL; 99 + long long b = 10000000000000000LL; 100 + long long _ = -1LL; 101 +END 102 +CASE(5) 103 + long long a = 1LL; 104 + long long b = 1LL; 105 + long long _ = 1LL; 106 +END 107 +CASE(6) 108 + long long a = 1LL; 109 + long long b = 99LL; 110 + long long _ = -1LL; 111 +END 112 + 113 +} 114 +// END CUT HERE
Added SRM/510-U/1B-U.cpp version [29ee29a34dc5af35]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class TheLuckyGameDivOne { public: 23 + vector<LL> all; 24 + void computeAll() 25 + { 26 + for(int len=1; len<=11; ++len) 27 + { 28 + for(int pat=0; pat<(1<<len); ++pat) 29 + { 30 + LL val = 0; 31 + for(int i=0; i<len; ++i) 32 + val = val*10 + ((pat&(1<<i)) ? 7 : 4); 33 + all.push_back(val); 34 + } 35 + } 36 + sort(all.begin(), all.end()); 37 + } 38 + 39 + int find(long long a, long long b, long long jLen, long long bLen) 40 + { 41 + computeAll(); 42 + 43 + pair<LL,LL> rng(a, a+bLen-1); 44 + vector< pair<pair<LL,LL>,int> > pt; 45 + pt.push_back(make_pair(rng, count_of(rng))); 46 + if( rng.second+1 <= b ) { 47 + pair<LL,LL> rngP1(rng.first+1,rng.second+1); 48 + pt.push_back(make_pair(rngP1, count_of(rngP1))); 49 + } 50 + for(;;) { 51 + rng = go_next(rng); 52 + if( rng.second > b ) 53 + break; 54 + pair<LL,LL> rngM1(rng.first-1,rng.second-1); 55 + pt.push_back(make_pair(rngM1, count_of(rngM1))); 56 + pt.push_back(make_pair(rng, count_of(rng))); 57 + if( rng.second+1 <= b ) { 58 + pair<LL,LL> rngP1(rng.first+1,rng.second+1); 59 + pt.push_back(make_pair(rngP1, count_of(rngP1))); 60 + } 61 + } 62 + sort(pt.begin(), pt.end()); 63 + pt.erase(unique(pt.begin(), pt.end()), pt.end()); 64 + 65 + const LL xLen = jLen - bLen + 1; 66 + int theMax = 0; 67 + for(size_t i=0; i<pt.size(); ++i) 68 + { 69 + int theMin = 0x7fffffff; 70 + for(size_t j=i; j<pt.size() && pt[j].first.first<pt[i].first.first+xLen; ++j) 71 + theMin = min(theMin, pt[j].second); 72 + theMax = max(theMax, theMin); 73 + } 74 + return theMax; 75 + } 76 + 77 + pair<LL,LL> go_next(pair<LL,LL> rng) 78 + { 79 + LL a = go_next(rng.first); 80 + LL b = go_next(rng.second); 81 + LL dif = min(a-rng.first, b-rng.second); 82 + return make_pair(rng.first+dif, rng.second+dif); 83 + } 84 + 85 + LL go_next(LL x) 86 + { 87 + return *upper_bound(all.begin(), all.end(), x); 88 + } 89 + 90 + int count_of(pair<LL,LL> rng) 91 + { 92 + LL a = rng.first; 93 + LL b = rng.second; 94 + vector<LL>::iterator s = lower_bound(all.begin(), all.end(), a); 95 + vector<LL>::iterator e = upper_bound(all.begin(), all.end(), b); 96 + return e-s; 97 + } 98 +}; 99 + 100 +// BEGIN CUT HERE 101 +#include <ctime> 102 +double start_time; string timer() 103 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 104 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 105 + { os << "{ "; 106 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 107 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 108 +void verify_case(const int& Expected, const int& Received) { 109 + bool ok = (Expected == Received); 110 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 111 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 112 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 113 +#define END verify_case(_, TheLuckyGameDivOne().find(a, b, jLen, bLen));} 114 +int main(){ 115 + 116 +CASE(0) 117 + long long a = 1LL; 118 + long long b = 10LL; 119 + long long jLen = 2LL; 120 + long long bLen = 1LL; 121 + int _ = 0; 122 +END 123 +CASE(1) 124 + long long a = 1LL; 125 + long long b = 100LL; 126 + long long jLen = 100LL; 127 + long long bLen = 100LL; 128 + int _ = 6; 129 +END 130 +CASE(2) 131 + long long a = 4LL; 132 + long long b = 8LL; 133 + long long jLen = 3LL; 134 + long long bLen = 2LL; 135 + int _ = 1; 136 +END 137 +CASE(3) 138 + long long a = 1LL; 139 + long long b = 100LL; 140 + long long jLen = 75LL; 141 + long long bLen = 50LL; 142 + int _ = 2; 143 +END 144 +CASE(4) 145 + long long a = 1LL; 146 + long long b = 1LL; 147 + long long jLen = 1LL; 148 + long long bLen = 1LL; 149 + int _ = 0; 150 +END 151 +CASE(5) 152 + long long a = 10000000000LL; 153 + long long b = 10000000000LL; 154 + long long jLen = 5000000000LL; 155 + long long bLen = 2000000000LL; 156 + int _ = -1; 157 +END 158 + 159 +} 160 +// END CUT HERE
Added SRM/510-U/1C-U.cpp version [7df1c0211e8d6875]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class TheLuckyBasesDivOne { public: 23 + set<LL> all; 24 + void computeAll() 25 + { 26 + for(int len=1; len<=15; ++len) 27 + { 28 + for(int pat=0; pat<(1<<len); ++pat) 29 + { 30 + LL val = 0; 31 + for(int i=0; i<len; ++i) 32 + val = val*10 + ((pat&(1<<i)) ? 7 : 4); 33 + all.insert(val); 34 + } 35 + } 36 + } 37 + 38 + long long find(long long n) 39 + { 40 + computeAll(); 41 + if( all.count(n) ) // if itself is lucky, then inf. 42 + return -1; 43 + 44 + LL cnt = 0; 45 + // 3 or more B-its 46 + for(LL B=2; B*B*B<=n; ++B) 47 + if( isLuckyBase(n, B) ) 48 + ++cnt; 49 + // 2 B-its 50 + for(set<LL>::iterator it=all.begin(); it!=all.end(); ++it) 51 + { 52 + LL r = n-*it; 53 + for(LL B=*it+1; B<=n/B && B*B<n; ++B) { 54 + if( r%B==0 && n/B<B && all.count(n/B) ) 55 + ++cnt; 56 + } 57 + } 58 + return cnt; 59 + } 60 + 61 + bool isLuckyBase(LL n, LL B) 62 + { 63 + for(;n; n/=B) 64 + if( !all.count(n%B) ) 65 + return false; 66 + return true; 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 long long& Expected, const long long& 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(_, TheLuckyBasesDivOne().find(n));} 84 +int main(){ 85 + 86 +CASE(0) 87 + long long n = 255LL; 88 + long long _ = 2LL; 89 +END 90 +CASE(1) 91 + long long n = 474LL; 92 + long long _ = -1LL; 93 +END 94 +CASE(2) 95 + long long n = 13LL; 96 + long long _ = 0LL; 97 +END 98 +CASE(3) 99 + long long n = 4748LL; 100 + long long _ = 5LL; 101 +END 102 +CASE(4) 103 + long long n = 1LL; 104 + long long _ = 0LL; 105 +END 106 +CASE(5) 107 + long long n = 10000000000000000LL; 108 + long long _ = -1LL; 109 +END 110 + 111 +} 112 +// END CUT HERE
Added SRM/TCO11-1/A.cpp version [3a5fb18ce90cdda6]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class TripleStrings { public: 23 + int getMinimumOperations(string init, string goal) 24 + { 25 + for(int i=0; i<=init.size(); ++i) 26 + if( init.substr(i, init.size()-i) == goal.substr(0, init.size()-i) ) 27 + return 2*i; 28 + assert(false); 29 + return -1; 30 + } 31 +}; 32 + 33 +// BEGIN CUT HERE 34 +#include <ctime> 35 +double start_time; string timer() 36 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 37 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 38 + { os << "{ "; 39 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 40 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 41 +void verify_case(const int& Expected, const int& Received) { 42 + bool ok = (Expected == Received); 43 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 44 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 45 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 46 +#define END verify_case(_, TripleStrings().getMinimumOperations(init, goal));} 47 +int main(){ 48 + 49 +CASE(0) 50 + string init = "ooxxox"; 51 + string goal = "xoxoxo"; 52 + int _ = 6; 53 +END 54 +CASE(1) 55 + string init = "oooxxoo"; 56 + string goal = "oooxxoo"; 57 + int _ = 0; 58 +END 59 +CASE(2) 60 + string init = "ox"; 61 + string goal = "xo"; 62 + int _ = 2; 63 +END 64 +CASE(3) 65 + string init = "ooxxooxx"; 66 + string goal = "xxoxoxoo"; 67 + int _ = 12; 68 +END 69 +CASE(4) 70 + string init = "oxxoxxoooxooooxxxoo"; 71 + string goal = "oxooooxxxooooxoxxxo"; 72 + int _ = 16; 73 +END 74 +CASE(5) 75 + string init = "xxxoxoxxooxooxoxooo"; 76 + string goal = "oxxooxxooxxoxoxooxo"; 77 + int _ = 36; 78 +END 79 +CASE(6) 80 + string init = "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox"; 81 + string goal = "oooooooooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxx"; 82 + int _ = -1; 83 +END 84 +CASE(7) 85 + string init = "o"; 86 + string goal = "o"; 87 + int _ = 0; 88 +END 89 +CASE(8) 90 + string init = "ox"; 91 + string goal = "xo"; 92 + int _ = 2; 93 +END 94 + 95 +} 96 +// END CUT HERE
Added SRM/TCO11-1/B.cpp version [f52c1a0b3c125396]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class MuddyRoad { public: 23 + double getExpectedValue(vector <int> road) 24 + { 25 + double dp[50][2]; 26 + for(size_t g=0; g<road.size(); ++g) 27 + for(int leftmud=0; leftmud<2; ++leftmud) 28 + if( g >= 2 ) 29 + { 30 + const double p = road[g-2] / 100.0; 31 + const double q = (leftmud==1 ? 1.0 : road[g-1] / 100.0); 32 + double e = 0; 33 + e += (1-p) * (1-q) * dp[g-2][0]; 34 + e += (1-p) * q * dp[g-2][0]; 35 + e += p * (1-q) * dp[g-1][1]; 36 + e += p * q * (1 + dp[g-2][0]); 37 + dp[g][leftmud] = e; 38 + } 39 + else if( g == 1 ) 40 + { 41 + dp[g][leftmud] = 0; 42 + } 43 + else 44 + { 45 + dp[g][leftmud] = 0; 46 + } 47 + return dp[road.size()-1][0]; 48 + } 49 +}; 50 + 51 +// BEGIN CUT HERE 52 +#include <ctime> 53 +double start_time; string timer() 54 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 55 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 56 + { os << "{ "; 57 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 58 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 59 +void verify_case(const double& Expected, const double& Received) { 60 + bool ok = (abs(Expected - Received) < 1e-9); 61 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 62 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 63 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 64 +#define END verify_case(_, MuddyRoad().getExpectedValue(road));} 65 +int main(){ 66 + 67 +CASE(0) 68 + int road_[] = {0, 60, 60, 0}; 69 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 70 + double _ = 0.36; 71 +END 72 +CASE(1) 73 + int road_[] = {0, 50, 50, 50, 50, 0}; 74 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 75 + double _ = 0.5625; 76 +END 77 +CASE(2) 78 + int road_[] = {0, 0, 100, 100, 100, 100, 100, 100, 0, 0, 100, 0}; 79 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 80 + double _ = 3.0; 81 +END 82 +CASE(3) 83 + int road_[] = {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0}; 84 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 85 + double _ = 1.7352539420031923; 86 +END 87 +CASE(4) 88 + int road_[] = {0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0}; 89 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 90 + double _ = 2.288125; 91 +END 92 +CASE(5) 93 +int road_[] = {0,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,0}; 94 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 95 + double _ = 1.0; 96 +END 97 +CASE(6) 98 + int road_[] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}; 99 + vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_)); 100 + double _ = -1; 101 +END 102 + 103 +} 104 +// END CUT HERE
Added SRM/TCO11-1/C.cpp version [7383f594e5758776]
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 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class IPv444 { public: 23 + struct Request 24 + { 25 + int x[4]; 26 + int y[4]; 27 + LL p; 28 + Request(const string& r, LL p) : p(p) 29 + { 30 + for(int d=0,s=0; d<4; ++d) 31 + { 32 + int e=s+1; 33 + while( e<r.size() && r[e]!='.' ) 34 + ++e; 35 + string num(r.begin()+s, r.begin()+e); 36 + if( num == "*" ) { 37 + x[d] = 0; 38 + y[d] = 1000; 39 + } 40 + else { 41 + x[d] = atoi(num.c_str()); 42 + y[d] = x[d]+1; 43 + } 44 + s = e+1; 45 + } 46 + } 47 + 48 + bool operator<(const Request& rhs) const 49 + { 50 + if( p != rhs.p ) 51 + return p < rhs.p; 52 + for(int d=0; d<4; ++d) 53 + if( x[d] != rhs.x[d] ) 54 + return x[d] < rhs.x[d]; 55 + return false; 56 + } 57 + }; 58 + 59 + long long getMaximumMoney(vector <string> request, vector <int> price) 60 + { 61 + vector<Request> req; 62 + for(size_t i=0; i<request.size(); ++i) 63 + req.push_back( Request(request[i], price[i]) ); 64 + sort(req.rbegin(), req.rend()); 65 + 66 + static const int MID = 2; 67 + 68 + vector<int> sig[4]; 69 + for(int d=0; d<MID; ++d) 70 + { 71 + set<int> sigs; 72 + for(int i=0; i<req.size(); ++i) 73 + { 74 + sigs.insert(req[i].x[d]); 75 + sigs.insert(req[i].y[d]); 76 + } 77 + sig[d].assign(sigs.begin(), sigs.end()); 78 + } 79 + 80 + LL sum = 0; 81 + int i[4]; 82 + for(i[0]=0; i[0]+1<sig[0].size(); ++i[0]) 83 + for(i[1]=0; i[1]+1<sig[1].size(); ++i[1]) 84 + { 85 + for(int d=MID; d<4; ++d) 86 + { 87 + set<int> sigs; 88 + for(int k=0; k<req.size(); ++k) 89 + { 90 + bool dame = false; 91 + for(int dd=0; dd<MID; ++dd) 92 + if( !(req[k].x[dd]<=sig[dd][i[dd]] && sig[dd][i[dd]+1]<=req[k].y[dd]) ) 93 + dame = true; 94 + if(!dame) 95 + { 96 + sigs.insert(req[k].x[d]); 97 + sigs.insert(req[k].y[d]); 98 + } 99 + } 100 + sig[d].assign(sigs.begin(), sigs.end()); 101 + } 102 + for(i[2]=0; i[2]+1<sig[2].size(); ++i[2]) 103 + for(i[3]=0; i[3]+1<sig[3].size(); ++i[3]) 104 + { 105 + LL p = 0; 106 + for(int k=0; k<req.size(); ++k) 107 + { 108 + bool dame = false; 109 + for(int d=0; d<4; ++d) 110 + if( !(req[k].x[d]<=sig[d][i[d]] && sig[d][i[d]+1]<=req[k].y[d]) ) 111 + dame = true; 112 + if(!dame) 113 + {p = req[k].p; break;} 114 + } 115 + LL a = p; 116 + for(int dd=0; dd<4; ++dd) 117 + a *= sig[dd][i[dd]+1] - sig[dd][i[dd]]; 118 + sum += a; 119 + } 120 + } 121 + return sum; 122 + } 123 +}; 124 + 125 +// BEGIN CUT HERE 126 +#include <ctime> 127 +double start_time; string timer() 128 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 129 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 130 + { os << "{ "; 131 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 132 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 133 +void verify_case(const long long& Expected, const long long& Received) { 134 + bool ok = (Expected == Received); 135 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 136 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 137 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 138 +#define END verify_case(_, IPv444().getMaximumMoney(request, price));} 139 +int main(){ 140 + 141 +CASE(0) 142 + string request_[] = {"66.37.210.86"}; 143 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 144 + int price_[] = {47}; 145 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 146 + long long _ = 47LL; 147 +END 148 +CASE(1) 149 + string request_[] = {"0.0.0.*", "0.0.0.3", "0.0.0.5"}; 150 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 151 + int price_[] = {1, 3, 9}; 152 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 153 + long long _ = 1010LL; 154 +END 155 +CASE(2) 156 + string request_[] = {"*.*.*.*", "123.456.789.0", "434.434.434.434", "999.*.999.*"}; 157 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 158 + int price_[] = {1, 5, 3, 6}; 159 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 160 + long long _ = 1000005000006LL; 161 +END 162 +CASE(3) 163 + string request_[] = {"*.*.999.999", "888.888.999.*", "888.888.*.999", "777.777.777.777", "777.*.*.777"}; 164 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 165 + int price_[] = {19, 33, 42, 777, 7}; 166 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 167 + long long _ = 26075718LL; 168 +END 169 +CASE(4) 170 + string request_[] = {"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*"}; 171 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 172 + int price_[] = {999999, 629851, 294016, 438090}; 173 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 174 + long long _ = 1361957076132LL; 175 +END 176 +CASE(5) 177 + string request_[] = { 178 + "1.1.1.1", 179 + "3.3.3.3", 180 + "5.5.5.5", 181 + "7.7.7.7", 182 + "9.9.9.9", 183 + "11.11.11.11", 184 + "13.13.13.13", 185 + "15.15.15.15", 186 + "17.17.17.17", 187 + "19.19.19.19", 188 + "21.21.21.21", 189 + "23.23.23.23", 190 + "25.25.25.25", 191 + "27.27.27.27", 192 + "29.29.29.29", 193 + "31.31.31.31", 194 + "33.33.33.33", 195 + "35.35.35.35", 196 + "37.37.37.37", 197 + "39.39.39.39", 198 + "41.41.41.41", 199 + "43.43.43.43", 200 + "45.45.45.45", 201 + "47.47.47.47", 202 + "49.49.49.49", 203 + "51.51.51.51", 204 + "53.53.53.53", 205 + "55.55.55.55", 206 + "57.57.57.57", 207 + "59.59.59.59", 208 +}; 209 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 210 + int price_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 211 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 212 + long long _ = -1LL; 213 +END 214 +/* 215 +CASE(6) 216 + string request_[] = ; 217 + vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 218 + int price_[] = ; 219 + vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 220 + long long _ = LL; 221 +END 222 +*/ 223 +} 224 +// END CUT HERE