8cbd8685a8 2019-07-19        kinaba: #include <iostream>
8cbd8685a8 2019-07-19        kinaba: #include <sstream>
8cbd8685a8 2019-07-19        kinaba: #include <iomanip>
8cbd8685a8 2019-07-19        kinaba: #include <vector>
8cbd8685a8 2019-07-19        kinaba: #include <string>
8cbd8685a8 2019-07-19        kinaba: #include <map>
8cbd8685a8 2019-07-19        kinaba: #include <set>
8cbd8685a8 2019-07-19        kinaba: #include <algorithm>
8cbd8685a8 2019-07-19        kinaba: #include <numeric>
8cbd8685a8 2019-07-19        kinaba: #include <iterator>
8cbd8685a8 2019-07-19        kinaba: #include <functional>
8cbd8685a8 2019-07-19        kinaba: #include <complex>
8cbd8685a8 2019-07-19        kinaba: #include <queue>
8cbd8685a8 2019-07-19        kinaba: #include <stack>
8cbd8685a8 2019-07-19        kinaba: #include <cmath>
8cbd8685a8 2019-07-19        kinaba: #include <cassert>
8cbd8685a8 2019-07-19        kinaba: #include <tuple>
8cbd8685a8 2019-07-19        kinaba: using namespace std;
8cbd8685a8 2019-07-19        kinaba: typedef long long LL;
8cbd8685a8 2019-07-19        kinaba: typedef complex<double> CMP;
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: class PrefixComposite { public:
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> minMax(long long A, long long B)
8cbd8685a8 2019-07-19        kinaba: 	{
8cbd8685a8 2019-07-19        kinaba: 		LL r = solve(B);
8cbd8685a8 2019-07-19        kinaba: 		if (r < A)
8cbd8685a8 2019-07-19        kinaba: 			return vector<LL>();
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 		LL L = A - 1, R = r;
8cbd8685a8 2019-07-19        kinaba: 		while(R-L>1) {
8cbd8685a8 2019-07-19        kinaba: 			LL C = (L + R) / 2;
8cbd8685a8 2019-07-19        kinaba: 			LL c = solve(C);
8cbd8685a8 2019-07-19        kinaba: 			if (c < A)
8cbd8685a8 2019-07-19        kinaba: 				L = C;
8cbd8685a8 2019-07-19        kinaba: 			else
8cbd8685a8 2019-07-19        kinaba: 				R = c;
8cbd8685a8 2019-07-19        kinaba: 		}
8cbd8685a8 2019-07-19        kinaba: 		return vector<LL>({ R, r });
8cbd8685a8 2019-07-19        kinaba: 	}
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 	// max such value <= B
8cbd8685a8 2019-07-19        kinaba: 	LL solve(LL B) {
8cbd8685a8 2019-07-19        kinaba: 		vector<int> bb;
8cbd8685a8 2019-07-19        kinaba: 		for(; B!=0; B/=10)
8cbd8685a8 2019-07-19        kinaba: 			bb.push_back(B % 10);
8cbd8685a8 2019-07-19        kinaba: 		reverse(bb.begin(), bb.end());
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 		function<LL(LL, int)> rec = [&](LL pref, int i) {
8cbd8685a8 2019-07-19        kinaba: 			if (i == bb.size())
8cbd8685a8 2019-07-19        kinaba: 				return pref;
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 			LL pp = pref * 10 + bb[i];
8cbd8685a8 2019-07-19        kinaba: 			if(is_composite(pp)) {
8cbd8685a8 2019-07-19        kinaba: 				LL r = rec(pp, i + 1);
8cbd8685a8 2019-07-19        kinaba: 				if (r)
8cbd8685a8 2019-07-19        kinaba: 					return r;
8cbd8685a8 2019-07-19        kinaba: 			}
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 			for (int k = bb[i] - 1; k >= 0; --k) {
8cbd8685a8 2019-07-19        kinaba: 				LL pp = pref * 10 + k;
8cbd8685a8 2019-07-19        kinaba: 				if (is_composite(pp)) {
8cbd8685a8 2019-07-19        kinaba: 					int n = bb.size() - i - 1;
8cbd8685a8 2019-07-19        kinaba: 					// get max from pp ++ [0-9]*n
8cbd8685a8 2019-07-19        kinaba: 					for (int j = 0; j < n; ++j)
8cbd8685a8 2019-07-19        kinaba: 						if (is_composite(pp*10+9))
8cbd8685a8 2019-07-19        kinaba: 							pp = pp*10+9;
8cbd8685a8 2019-07-19        kinaba: 						else
8cbd8685a8 2019-07-19        kinaba: 							pp = pp*10+8;
8cbd8685a8 2019-07-19        kinaba: 					return pp;
8cbd8685a8 2019-07-19        kinaba: 				}
8cbd8685a8 2019-07-19        kinaba: 			}
8cbd8685a8 2019-07-19        kinaba: 			return 0LL;
8cbd8685a8 2019-07-19        kinaba: 		};
8cbd8685a8 2019-07-19        kinaba: 		return rec(0, 0);
8cbd8685a8 2019-07-19        kinaba: 	}
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: 	bool is_composite(LL v)
8cbd8685a8 2019-07-19        kinaba: 	{
8cbd8685a8 2019-07-19        kinaba: 		if (v == 0)
8cbd8685a8 2019-07-19        kinaba: 			return true;
8cbd8685a8 2019-07-19        kinaba: 		for (LL p = 2; p*p <= v; ++p)
8cbd8685a8 2019-07-19        kinaba: 			if (v%p == 0)
8cbd8685a8 2019-07-19        kinaba: 				return true;
8cbd8685a8 2019-07-19        kinaba: 		return false;
8cbd8685a8 2019-07-19        kinaba: 	}
8cbd8685a8 2019-07-19        kinaba: };
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: // BEGIN CUT HERE
8cbd8685a8 2019-07-19        kinaba: #include <ctime>
8cbd8685a8 2019-07-19        kinaba: double start_time; string timer()
8cbd8685a8 2019-07-19        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
8cbd8685a8 2019-07-19        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
8cbd8685a8 2019-07-19        kinaba:  { os << "{ ";
8cbd8685a8 2019-07-19        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
8cbd8685a8 2019-07-19        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
8cbd8685a8 2019-07-19        kinaba: void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
8cbd8685a8 2019-07-19        kinaba:  bool ok = (Expected == Received);
8cbd8685a8 2019-07-19        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
8cbd8685a8 2019-07-19        kinaba:  cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
8cbd8685a8 2019-07-19        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
8cbd8685a8 2019-07-19        kinaba: #define END	 verify_case(_, PrefixComposite().minMax(A, B));}
8cbd8685a8 2019-07-19        kinaba: int main(){
8cbd8685a8 2019-07-19        kinaba: 
8cbd8685a8 2019-07-19        kinaba: CASE(0)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 1LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 3LL;
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(1)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 1LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 4LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = {4, 4 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(2)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 123LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 838LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = {400, 828 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(3)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 409LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 87343LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = {420, 87343 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(4)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 979797LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 979898LL;
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(5)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 600LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 703LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = {600, 699 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(6)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 1LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 100000000000LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = {4, 99999999999 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(7)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 37337999LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 37337999LL;
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(8)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 22LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 39LL;
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(9)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 600LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 699LL;
8cbd8685a8 2019-07-19        kinaba: 	long long __[] = { 600, 699 };
8cbd8685a8 2019-07-19        kinaba: 	  vector<long long> _(__, __+sizeof(__)/sizeof(*__));
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(10)
8cbd8685a8 2019-07-19        kinaba: 	long long A = 1LL;
8cbd8685a8 2019-07-19        kinaba: 	long long B = 1LL;
8cbd8685a8 2019-07-19        kinaba: 	vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: CASE(10)
8cbd8685a8 2019-07-19        kinaba: long long A = 1LL;
8cbd8685a8 2019-07-19        kinaba: long long B = 6LL;
8cbd8685a8 2019-07-19        kinaba: vector<long long> _;
8cbd8685a8 2019-07-19        kinaba: END
8cbd8685a8 2019-07-19        kinaba: }
8cbd8685a8 2019-07-19        kinaba: // END CUT HERE