ba35b3a9cf 2011-06-25 kinaba: #include <iostream> ba35b3a9cf 2011-06-25 kinaba: #include <sstream> ba35b3a9cf 2011-06-25 kinaba: #include <iomanip> ba35b3a9cf 2011-06-25 kinaba: #include <vector> ba35b3a9cf 2011-06-25 kinaba: #include <string> ba35b3a9cf 2011-06-25 kinaba: #include <map> ba35b3a9cf 2011-06-25 kinaba: #include <set> ba35b3a9cf 2011-06-25 kinaba: #include <algorithm> ba35b3a9cf 2011-06-25 kinaba: #include <numeric> ba35b3a9cf 2011-06-25 kinaba: #include <iterator> ba35b3a9cf 2011-06-25 kinaba: #include <functional> ba35b3a9cf 2011-06-25 kinaba: #include <complex> ba35b3a9cf 2011-06-25 kinaba: #include <queue> ba35b3a9cf 2011-06-25 kinaba: #include <stack> ba35b3a9cf 2011-06-25 kinaba: #include <cmath> ba35b3a9cf 2011-06-25 kinaba: #include <cassert> ba35b3a9cf 2011-06-25 kinaba: #include <cstring> ba35b3a9cf 2011-06-25 kinaba: using namespace std; ba35b3a9cf 2011-06-25 kinaba: typedef long long LL; ba35b3a9cf 2011-06-25 kinaba: typedef complex<double> CMP; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: class TheLuckyGameDivOne { public: ba35b3a9cf 2011-06-25 kinaba: vector<LL> all; ba35b3a9cf 2011-06-25 kinaba: void computeAll() ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int len=1; len<=11; ++len) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int pat=0; pat<(1<<len); ++pat) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL val = 0; ba35b3a9cf 2011-06-25 kinaba: for(int i=0; i<len; ++i) ba35b3a9cf 2011-06-25 kinaba: val = val*10 + ((pat&(1<<i)) ? 7 : 4); ba35b3a9cf 2011-06-25 kinaba: all.push_back(val); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: sort(all.begin(), all.end()); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: int find(long long a, long long b, long long jLen, long long bLen) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: computeAll(); ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: pair<LL,LL> rng(a, a+bLen-1); ba35b3a9cf 2011-06-25 kinaba: vector< pair<pair<LL,LL>,int> > pt; ba35b3a9cf 2011-06-25 kinaba: pt.push_back(make_pair(rng, count_of(rng))); ba35b3a9cf 2011-06-25 kinaba: if( rng.second+1 <= b ) { ba35b3a9cf 2011-06-25 kinaba: pair<LL,LL> rngP1(rng.first+1,rng.second+1); ba35b3a9cf 2011-06-25 kinaba: pt.push_back(make_pair(rngP1, count_of(rngP1))); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: for(;;) { ba35b3a9cf 2011-06-25 kinaba: rng = go_next(rng); ba35b3a9cf 2011-06-25 kinaba: if( rng.second > b ) ba35b3a9cf 2011-06-25 kinaba: break; ba35b3a9cf 2011-06-25 kinaba: pair<LL,LL> rngM1(rng.first-1,rng.second-1); ba35b3a9cf 2011-06-25 kinaba: pt.push_back(make_pair(rngM1, count_of(rngM1))); ba35b3a9cf 2011-06-25 kinaba: pt.push_back(make_pair(rng, count_of(rng))); ba35b3a9cf 2011-06-25 kinaba: if( rng.second+1 <= b ) { ba35b3a9cf 2011-06-25 kinaba: pair<LL,LL> rngP1(rng.first+1,rng.second+1); ba35b3a9cf 2011-06-25 kinaba: pt.push_back(make_pair(rngP1, count_of(rngP1))); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: sort(pt.begin(), pt.end()); ba35b3a9cf 2011-06-25 kinaba: pt.erase(unique(pt.begin(), pt.end()), pt.end()); ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: const LL xLen = jLen - bLen + 1; ba35b3a9cf 2011-06-25 kinaba: int theMax = 0; ba35b3a9cf 2011-06-25 kinaba: for(size_t i=0; i<pt.size(); ++i) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: int theMin = 0x7fffffff; ba35b3a9cf 2011-06-25 kinaba: for(size_t j=i; j<pt.size() && pt[j].first.first<pt[i].first.first+xLen; ++j) ba35b3a9cf 2011-06-25 kinaba: theMin = min(theMin, pt[j].second); ba35b3a9cf 2011-06-25 kinaba: theMax = max(theMax, theMin); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: return theMax; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: pair<LL,LL> go_next(pair<LL,LL> rng) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL a = go_next(rng.first); ba35b3a9cf 2011-06-25 kinaba: LL b = go_next(rng.second); ba35b3a9cf 2011-06-25 kinaba: LL dif = min(a-rng.first, b-rng.second); ba35b3a9cf 2011-06-25 kinaba: return make_pair(rng.first+dif, rng.second+dif); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: LL go_next(LL x) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: return *upper_bound(all.begin(), all.end(), x); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: int count_of(pair<LL,LL> rng) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL a = rng.first; ba35b3a9cf 2011-06-25 kinaba: LL b = rng.second; ba35b3a9cf 2011-06-25 kinaba: vector<LL>::iterator s = lower_bound(all.begin(), all.end(), a); ba35b3a9cf 2011-06-25 kinaba: vector<LL>::iterator e = upper_bound(all.begin(), all.end(), b); ba35b3a9cf 2011-06-25 kinaba: return e-s; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: }; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: // BEGIN CUT HERE ba35b3a9cf 2011-06-25 kinaba: #include <ctime> ba35b3a9cf 2011-06-25 kinaba: double start_time; string timer() ba35b3a9cf 2011-06-25 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ba35b3a9cf 2011-06-25 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ba35b3a9cf 2011-06-25 kinaba: { os << "{ "; ba35b3a9cf 2011-06-25 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ba35b3a9cf 2011-06-25 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ba35b3a9cf 2011-06-25 kinaba: void verify_case(const int& Expected, const int& Received) { ba35b3a9cf 2011-06-25 kinaba: bool ok = (Expected == Received); ba35b3a9cf 2011-06-25 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ba35b3a9cf 2011-06-25 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ba35b3a9cf 2011-06-25 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ba35b3a9cf 2011-06-25 kinaba: #define END verify_case(_, TheLuckyGameDivOne().find(a, b, jLen, bLen));} ba35b3a9cf 2011-06-25 kinaba: int main(){ ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: CASE(0) ba35b3a9cf 2011-06-25 kinaba: long long a = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 10LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 2LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 1LL; ba35b3a9cf 2011-06-25 kinaba: int _ = 0; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(1) ba35b3a9cf 2011-06-25 kinaba: long long a = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 100LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 100LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 100LL; ba35b3a9cf 2011-06-25 kinaba: int _ = 6; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(2) ba35b3a9cf 2011-06-25 kinaba: long long a = 4LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 8LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 3LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 2LL; ba35b3a9cf 2011-06-25 kinaba: int _ = 1; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(3) ba35b3a9cf 2011-06-25 kinaba: long long a = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 100LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 75LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 50LL; ba35b3a9cf 2011-06-25 kinaba: int _ = 2; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(4) ba35b3a9cf 2011-06-25 kinaba: long long a = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 1LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 1LL; ba35b3a9cf 2011-06-25 kinaba: int _ = 0; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(5) ba35b3a9cf 2011-06-25 kinaba: long long a = 10000000000LL; ba35b3a9cf 2011-06-25 kinaba: long long b = 10000000000LL; ba35b3a9cf 2011-06-25 kinaba: long long jLen = 5000000000LL; ba35b3a9cf 2011-06-25 kinaba: long long bLen = 2000000000LL; ba35b3a9cf 2011-06-25 kinaba: int _ = -1; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: // END CUT HERE