ADDED SRM/510-U/1A.cpp
Index: SRM/510-U/1A.cpp
==================================================================
--- SRM/510-U/1A.cpp
+++ SRM/510-U/1A.cpp
@@ -0,0 +1,114 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class TheAlmostLuckyNumbersDivOne { public:
+ LL rec(LL n, int miss_atmost=1, LL prefix=0)
+ {
+ if( n<prefix || miss_atmost<0 )
+ return 0;
+ LL cnt = (prefix==0?0:1);
+ for(int i=(prefix==0?1:0); i<=9; ++i)
+ cnt += rec(n, miss_atmost-(i==4||i==7?0:1), prefix*10+i);
+ return cnt;
+ }
+ LL find(LL a, LL b)
+ {
+ return rec(b) - rec(a-1);
+ LL cnt = 0;
+ for(int len=1; len<=16; ++len) // ���� len ��
+ for(int pat=0; pat<(1<<len); ++pat) // �r�b�g�p�^�[����S��
+ {
+ // [0,1] -> [4,7] �ɕς���� lucky number �̑S����
+ LL val = 0;
+ for(int i=0; i<len; ++i)
+ val = val*10 + (pat&(1<<i) ? 7 : 4);
+ if( a<=val && val<=b )
+ ++cnt;
+
+ // Almost Lucky Number �� 1 �ӏ��Ⴄ
+ for(int m=0; m<len; ++m) if(pat&(1<<m)) // 7 ���
+ for(int mTo=(m==0?1:0); mTo<=9; ++mTo) if(mTo!=4 && mTo!=7) // 0-3,5-6,8-9 �ɂ��Ă݂�
+ {
+ LL val = 0;
+ for(int i=0; i<len; ++i)
+ val = val*10 + (i==m ? mTo : (pat&(1<<i)) ? 7 : 4);
+ if( a<=val && val<=b )
+ ++cnt;
+ }
+ }
+ return cnt;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const long long& Expected, const long long& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, TheAlmostLuckyNumbersDivOne().find(a, b));}
+int main(){
+
+CASE(0)
+ long long a = 4LL;
+ long long b = 7LL;
+ long long _ = 4LL;
+END
+CASE(1)
+ long long a = 8LL;
+ long long b = 19LL;
+ long long _ = 4LL;
+END
+CASE(2)
+ long long a = 28LL;
+ long long b = 33LL;
+ long long _ = 0LL;
+END
+CASE(3)
+ long long a = 12345678900LL;
+ long long b = 98765432100LL;
+ long long _ = 91136LL;
+END
+CASE(4)
+ long long a = 1LL;
+ long long b = 10000000000000000LL;
+ long long _ = -1LL;
+END
+CASE(5)
+ long long a = 1LL;
+ long long b = 1LL;
+ long long _ = 1LL;
+END
+CASE(6)
+ long long a = 1LL;
+ long long b = 99LL;
+ long long _ = -1LL;
+END
+
+}
+// END CUT HERE
ADDED SRM/510-U/1B-U.cpp
Index: SRM/510-U/1B-U.cpp
==================================================================
--- SRM/510-U/1B-U.cpp
+++ SRM/510-U/1B-U.cpp
@@ -0,0 +1,160 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class TheLuckyGameDivOne { public:
+ vector<LL> all;
+ void computeAll()
+ {
+ for(int len=1; len<=11; ++len)
+ {
+ for(int pat=0; pat<(1<<len); ++pat)
+ {
+ LL val = 0;
+ for(int i=0; i<len; ++i)
+ val = val*10 + ((pat&(1<<i)) ? 7 : 4);
+ all.push_back(val);
+ }
+ }
+ sort(all.begin(), all.end());
+ }
+
+ int find(long long a, long long b, long long jLen, long long bLen)
+ {
+ computeAll();
+
+ pair<LL,LL> rng(a, a+bLen-1);
+ vector< pair<pair<LL,LL>,int> > pt;
+ pt.push_back(make_pair(rng, count_of(rng)));
+ if( rng.second+1 <= b ) {
+ pair<LL,LL> rngP1(rng.first+1,rng.second+1);
+ pt.push_back(make_pair(rngP1, count_of(rngP1)));
+ }
+ for(;;) {
+ rng = go_next(rng);
+ if( rng.second > b )
+ break;
+ pair<LL,LL> rngM1(rng.first-1,rng.second-1);
+ pt.push_back(make_pair(rngM1, count_of(rngM1)));
+ pt.push_back(make_pair(rng, count_of(rng)));
+ if( rng.second+1 <= b ) {
+ pair<LL,LL> rngP1(rng.first+1,rng.second+1);
+ pt.push_back(make_pair(rngP1, count_of(rngP1)));
+ }
+ }
+ sort(pt.begin(), pt.end());
+ pt.erase(unique(pt.begin(), pt.end()), pt.end());
+
+ const LL xLen = jLen - bLen + 1;
+ int theMax = 0;
+ for(size_t i=0; i<pt.size(); ++i)
+ {
+ int theMin = 0x7fffffff;
+ for(size_t j=i; j<pt.size() && pt[j].first.first<pt[i].first.first+xLen; ++j)
+ theMin = min(theMin, pt[j].second);
+ theMax = max(theMax, theMin);
+ }
+ return theMax;
+ }
+
+ pair<LL,LL> go_next(pair<LL,LL> rng)
+ {
+ LL a = go_next(rng.first);
+ LL b = go_next(rng.second);
+ LL dif = min(a-rng.first, b-rng.second);
+ return make_pair(rng.first+dif, rng.second+dif);
+ }
+
+ LL go_next(LL x)
+ {
+ return *upper_bound(all.begin(), all.end(), x);
+ }
+
+ int count_of(pair<LL,LL> rng)
+ {
+ LL a = rng.first;
+ LL b = rng.second;
+ vector<LL>::iterator s = lower_bound(all.begin(), all.end(), a);
+ vector<LL>::iterator e = upper_bound(all.begin(), all.end(), b);
+ return e-s;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, TheLuckyGameDivOne().find(a, b, jLen, bLen));}
+int main(){
+
+CASE(0)
+ long long a = 1LL;
+ long long b = 10LL;
+ long long jLen = 2LL;
+ long long bLen = 1LL;
+ int _ = 0;
+END
+CASE(1)
+ long long a = 1LL;
+ long long b = 100LL;
+ long long jLen = 100LL;
+ long long bLen = 100LL;
+ int _ = 6;
+END
+CASE(2)
+ long long a = 4LL;
+ long long b = 8LL;
+ long long jLen = 3LL;
+ long long bLen = 2LL;
+ int _ = 1;
+END
+CASE(3)
+ long long a = 1LL;
+ long long b = 100LL;
+ long long jLen = 75LL;
+ long long bLen = 50LL;
+ int _ = 2;
+END
+CASE(4)
+ long long a = 1LL;
+ long long b = 1LL;
+ long long jLen = 1LL;
+ long long bLen = 1LL;
+ int _ = 0;
+END
+CASE(5)
+ long long a = 10000000000LL;
+ long long b = 10000000000LL;
+ long long jLen = 5000000000LL;
+ long long bLen = 2000000000LL;
+ int _ = -1;
+END
+
+}
+// END CUT HERE
ADDED SRM/510-U/1C-U.cpp
Index: SRM/510-U/1C-U.cpp
==================================================================
--- SRM/510-U/1C-U.cpp
+++ SRM/510-U/1C-U.cpp
@@ -0,0 +1,112 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class TheLuckyBasesDivOne { public:
+ set<LL> all;
+ void computeAll()
+ {
+ for(int len=1; len<=15; ++len)
+ {
+ for(int pat=0; pat<(1<<len); ++pat)
+ {
+ LL val = 0;
+ for(int i=0; i<len; ++i)
+ val = val*10 + ((pat&(1<<i)) ? 7 : 4);
+ all.insert(val);
+ }
+ }
+ }
+
+ long long find(long long n)
+ {
+ computeAll();
+ if( all.count(n) ) // if itself is lucky, then inf.
+ return -1;
+
+ LL cnt = 0;
+ // 3 or more B-its
+ for(LL B=2; B*B*B<=n; ++B)
+ if( isLuckyBase(n, B) )
+ ++cnt;
+ // 2 B-its
+ for(set<LL>::iterator it=all.begin(); it!=all.end(); ++it)
+ {
+ LL r = n-*it;
+ for(LL B=*it+1; B<=n/B && B*B<n; ++B) {
+ if( r%B==0 && n/B<B && all.count(n/B) )
+ ++cnt;
+ }
+ }
+ return cnt;
+ }
+
+ bool isLuckyBase(LL n, LL B)
+ {
+ for(;n; n/=B)
+ if( !all.count(n%B) )
+ return false;
+ return true;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const long long& Expected, const long long& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, TheLuckyBasesDivOne().find(n));}
+int main(){
+
+CASE(0)
+ long long n = 255LL;
+ long long _ = 2LL;
+END
+CASE(1)
+ long long n = 474LL;
+ long long _ = -1LL;
+END
+CASE(2)
+ long long n = 13LL;
+ long long _ = 0LL;
+END
+CASE(3)
+ long long n = 4748LL;
+ long long _ = 5LL;
+END
+CASE(4)
+ long long n = 1LL;
+ long long _ = 0LL;
+END
+CASE(5)
+ long long n = 10000000000000000LL;
+ long long _ = -1LL;
+END
+
+}
+// END CUT HERE
ADDED SRM/TCO11-1/A.cpp
Index: SRM/TCO11-1/A.cpp
==================================================================
--- SRM/TCO11-1/A.cpp
+++ SRM/TCO11-1/A.cpp
@@ -0,0 +1,96 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class TripleStrings { public:
+ int getMinimumOperations(string init, string goal)
+ {
+ for(int i=0; i<=init.size(); ++i)
+ if( init.substr(i, init.size()-i) == goal.substr(0, init.size()-i) )
+ return 2*i;
+ assert(false);
+ return -1;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, TripleStrings().getMinimumOperations(init, goal));}
+int main(){
+
+CASE(0)
+ string init = "ooxxox";
+ string goal = "xoxoxo";
+ int _ = 6;
+END
+CASE(1)
+ string init = "oooxxoo";
+ string goal = "oooxxoo";
+ int _ = 0;
+END
+CASE(2)
+ string init = "ox";
+ string goal = "xo";
+ int _ = 2;
+END
+CASE(3)
+ string init = "ooxxooxx";
+ string goal = "xxoxoxoo";
+ int _ = 12;
+END
+CASE(4)
+ string init = "oxxoxxoooxooooxxxoo";
+ string goal = "oxooooxxxooooxoxxxo";
+ int _ = 16;
+END
+CASE(5)
+ string init = "xxxoxoxxooxooxoxooo";
+ string goal = "oxxooxxooxxoxoxooxo";
+ int _ = 36;
+END
+CASE(6)
+ string init = "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox";
+ string goal = "oooooooooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxx";
+ int _ = -1;
+END
+CASE(7)
+ string init = "o";
+ string goal = "o";
+ int _ = 0;
+END
+CASE(8)
+ string init = "ox";
+ string goal = "xo";
+ int _ = 2;
+END
+
+}
+// END CUT HERE
ADDED SRM/TCO11-1/B.cpp
Index: SRM/TCO11-1/B.cpp
==================================================================
--- SRM/TCO11-1/B.cpp
+++ SRM/TCO11-1/B.cpp
@@ -0,0 +1,104 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class MuddyRoad { public:
+ double getExpectedValue(vector <int> road)
+ {
+ double dp[50][2];
+ for(size_t g=0; g<road.size(); ++g)
+ for(int leftmud=0; leftmud<2; ++leftmud)
+ if( g >= 2 )
+ {
+ const double p = road[g-2] / 100.0;
+ const double q = (leftmud==1 ? 1.0 : road[g-1] / 100.0);
+ double e = 0;
+ e += (1-p) * (1-q) * dp[g-2][0];
+ e += (1-p) * q * dp[g-2][0];
+ e += p * (1-q) * dp[g-1][1];
+ e += p * q * (1 + dp[g-2][0]);
+ dp[g][leftmud] = e;
+ }
+ else if( g == 1 )
+ {
+ dp[g][leftmud] = 0;
+ }
+ else
+ {
+ dp[g][leftmud] = 0;
+ }
+ return dp[road.size()-1][0];
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, MuddyRoad().getExpectedValue(road));}
+int main(){
+
+CASE(0)
+ int road_[] = {0, 60, 60, 0};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 0.36;
+END
+CASE(1)
+ int road_[] = {0, 50, 50, 50, 50, 0};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 0.5625;
+END
+CASE(2)
+ int road_[] = {0, 0, 100, 100, 100, 100, 100, 100, 0, 0, 100, 0};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 3.0;
+END
+CASE(3)
+ int road_[] = {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 1.7352539420031923;
+END
+CASE(4)
+ int road_[] = {0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 2.288125;
+END
+CASE(5)
+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};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = 1.0;
+END
+CASE(6)
+ 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};
+ vector <int> road(road_, road_+sizeof(road_)/sizeof(*road_));
+ double _ = -1;
+END
+
+}
+// END CUT HERE
ADDED SRM/TCO11-1/C.cpp
Index: SRM/TCO11-1/C.cpp
==================================================================
--- SRM/TCO11-1/C.cpp
+++ SRM/TCO11-1/C.cpp
@@ -0,0 +1,224 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class IPv444 { public:
+ struct Request
+ {
+ int x[4];
+ int y[4];
+ LL p;
+ Request(const string& r, LL p) : p(p)
+ {
+ for(int d=0,s=0; d<4; ++d)
+ {
+ int e=s+1;
+ while( e<r.size() && r[e]!='.' )
+ ++e;
+ string num(r.begin()+s, r.begin()+e);
+ if( num == "*" ) {
+ x[d] = 0;
+ y[d] = 1000;
+ }
+ else {
+ x[d] = atoi(num.c_str());
+ y[d] = x[d]+1;
+ }
+ s = e+1;
+ }
+ }
+
+ bool operator<(const Request& rhs) const
+ {
+ if( p != rhs.p )
+ return p < rhs.p;
+ for(int d=0; d<4; ++d)
+ if( x[d] != rhs.x[d] )
+ return x[d] < rhs.x[d];
+ return false;
+ }
+ };
+
+ long long getMaximumMoney(vector <string> request, vector <int> price)
+ {
+ vector<Request> req;
+ for(size_t i=0; i<request.size(); ++i)
+ req.push_back( Request(request[i], price[i]) );
+ sort(req.rbegin(), req.rend());
+
+ static const int MID = 2;
+
+ vector<int> sig[4];
+ for(int d=0; d<MID; ++d)
+ {
+ set<int> sigs;
+ for(int i=0; i<req.size(); ++i)
+ {
+ sigs.insert(req[i].x[d]);
+ sigs.insert(req[i].y[d]);
+ }
+ sig[d].assign(sigs.begin(), sigs.end());
+ }
+
+ LL sum = 0;
+ int i[4];
+ for(i[0]=0; i[0]+1<sig[0].size(); ++i[0])
+ for(i[1]=0; i[1]+1<sig[1].size(); ++i[1])
+ {
+ for(int d=MID; d<4; ++d)
+ {
+ set<int> sigs;
+ for(int k=0; k<req.size(); ++k)
+ {
+ bool dame = false;
+ for(int dd=0; dd<MID; ++dd)
+ if( !(req[k].x[dd]<=sig[dd][i[dd]] && sig[dd][i[dd]+1]<=req[k].y[dd]) )
+ dame = true;
+ if(!dame)
+ {
+ sigs.insert(req[k].x[d]);
+ sigs.insert(req[k].y[d]);
+ }
+ }
+ sig[d].assign(sigs.begin(), sigs.end());
+ }
+ for(i[2]=0; i[2]+1<sig[2].size(); ++i[2])
+ for(i[3]=0; i[3]+1<sig[3].size(); ++i[3])
+ {
+ LL p = 0;
+ for(int k=0; k<req.size(); ++k)
+ {
+ bool dame = false;
+ for(int d=0; d<4; ++d)
+ if( !(req[k].x[d]<=sig[d][i[d]] && sig[d][i[d]+1]<=req[k].y[d]) )
+ dame = true;
+ if(!dame)
+ {p = req[k].p; break;}
+ }
+ LL a = p;
+ for(int dd=0; dd<4; ++dd)
+ a *= sig[dd][i[dd]+1] - sig[dd][i[dd]];
+ sum += a;
+ }
+ }
+ return sum;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+ os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const long long& Expected, const long long& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END verify_case(_, IPv444().getMaximumMoney(request, price));}
+int main(){
+
+CASE(0)
+ string request_[] = {"66.37.210.86"};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = {47};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = 47LL;
+END
+CASE(1)
+ string request_[] = {"0.0.0.*", "0.0.0.3", "0.0.0.5"};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = {1, 3, 9};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = 1010LL;
+END
+CASE(2)
+ string request_[] = {"*.*.*.*", "123.456.789.0", "434.434.434.434", "999.*.999.*"};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = {1, 5, 3, 6};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = 1000005000006LL;
+END
+CASE(3)
+ string request_[] = {"*.*.999.999", "888.888.999.*", "888.888.*.999", "777.777.777.777", "777.*.*.777"};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = {19, 33, 42, 777, 7};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = 26075718LL;
+END
+CASE(4)
+ string request_[] = {"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*"};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = {999999, 629851, 294016, 438090};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = 1361957076132LL;
+END
+CASE(5)
+ string request_[] = {
+ "1.1.1.1",
+ "3.3.3.3",
+ "5.5.5.5",
+ "7.7.7.7",
+ "9.9.9.9",
+ "11.11.11.11",
+ "13.13.13.13",
+ "15.15.15.15",
+ "17.17.17.17",
+ "19.19.19.19",
+ "21.21.21.21",
+ "23.23.23.23",
+ "25.25.25.25",
+ "27.27.27.27",
+ "29.29.29.29",
+ "31.31.31.31",
+ "33.33.33.33",
+ "35.35.35.35",
+ "37.37.37.37",
+ "39.39.39.39",
+ "41.41.41.41",
+ "43.43.43.43",
+ "45.45.45.45",
+ "47.47.47.47",
+ "49.49.49.49",
+ "51.51.51.51",
+ "53.53.53.53",
+ "55.55.55.55",
+ "57.57.57.57",
+ "59.59.59.59",
+};
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ 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};
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = -1LL;
+END
+/*
+CASE(6)
+ string request_[] = ;
+ vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_));
+ int price_[] = ;
+ vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_));
+ long long _ = LL;
+END
+*/
+}
+// END CUT HERE