d796dcebe4 2019-08-11        kinaba: #include <iostream>
d796dcebe4 2019-08-11        kinaba: #include <sstream>
d796dcebe4 2019-08-11        kinaba: #include <iomanip>
d796dcebe4 2019-08-11        kinaba: #include <vector>
d796dcebe4 2019-08-11        kinaba: #include <string>
d796dcebe4 2019-08-11        kinaba: #include <map>
d796dcebe4 2019-08-11        kinaba: #include <set>
d796dcebe4 2019-08-11        kinaba: #include <algorithm>
d796dcebe4 2019-08-11        kinaba: #include <numeric>
d796dcebe4 2019-08-11        kinaba: #include <iterator>
d796dcebe4 2019-08-11        kinaba: #include <functional>
d796dcebe4 2019-08-11        kinaba: #include <complex>
d796dcebe4 2019-08-11        kinaba: #include <queue>
d796dcebe4 2019-08-11        kinaba: #include <stack>
d796dcebe4 2019-08-11        kinaba: #include <cmath>
d796dcebe4 2019-08-11        kinaba: #include <cassert>
d796dcebe4 2019-08-11        kinaba: #include <tuple>
d796dcebe4 2019-08-11        kinaba: using namespace std;
d796dcebe4 2019-08-11        kinaba: typedef long long LL;
d796dcebe4 2019-08-11        kinaba: typedef complex<double> CMP;
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: class ReProduct { public:
d796dcebe4 2019-08-11        kinaba: 	long long minimize(vector <int> base, int goal)
d796dcebe4 2019-08-11        kinaba: 	{
d796dcebe4 2019-08-11        kinaba: 		vector<tuple<LL,int,int,int,int>> cand(1, make_tuple(0LL,-1,-1,-1,-1));
d796dcebe4 2019-08-11        kinaba: 		for (LL a = 1,ai=0; a <= 1000000000000000000LL; a *= 2,++ai)
d796dcebe4 2019-08-11        kinaba: 			for (LL b = a,bi=0; b <= 1000000000000000000LL; b *= 3,++bi)
d796dcebe4 2019-08-11        kinaba: 				for (LL c = b,ci=0; c <= 1000000000000000000LL; c *= 5,++ci)
d796dcebe4 2019-08-11        kinaba: 					for (LL d = c,di=0; d <= 1000000000000000000LL; d *= 7,++di)
d796dcebe4 2019-08-11        kinaba: 						cand.emplace_back(d, ai,bi,ci,di);
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: 		vector<LL> vs;
d796dcebe4 2019-08-11        kinaba: 		for (auto cc : cand) {
d796dcebe4 2019-08-11        kinaba: 			LL c = get<0>(cc);
d796dcebe4 2019-08-11        kinaba: 			LL v = value(c, base);
d796dcebe4 2019-08-11        kinaba: 			if (v == goal)
d796dcebe4 2019-08-11        kinaba: 				vs.push_back(c);
d796dcebe4 2019-08-11        kinaba: 			if (v + 1 == goal)
d796dcebe4 2019-08-11        kinaba: 				if (c == 0)
d796dcebe4 2019-08-11        kinaba: 					vs.push_back(10);
d796dcebe4 2019-08-11        kinaba: 				else if (c==1)
d796dcebe4 2019-08-11        kinaba: 					vs.push_back(11);
d796dcebe4 2019-08-11        kinaba: 				else {
d796dcebe4 2019-08-11        kinaba: 					int p2 = get<1>(cc);
d796dcebe4 2019-08-11        kinaba: 					int p3 = get<2>(cc);
d796dcebe4 2019-08-11        kinaba: 					int p5 = get<3>(cc);
d796dcebe4 2019-08-11        kinaba: 					int p7 = get<4>(cc);
d796dcebe4 2019-08-11        kinaba: 					if (p2 + p3 + p5 + p7 >= 2) {
d796dcebe4 2019-08-11        kinaba: 						vector<int> ds;
d796dcebe4 2019-08-11        kinaba: 						for (int _ = 0; _ < p5; ++_) ds.push_back(5);
d796dcebe4 2019-08-11        kinaba: 						for (int _ = 0; _ < p7; ++_) ds.push_back(7);
d796dcebe4 2019-08-11        kinaba: 						if (ds.empty() && p2 + p3 == 2) {
d796dcebe4 2019-08-11        kinaba: 							for (int _ = 0; _ < p2; ++_) ds.push_back(2);
d796dcebe4 2019-08-11        kinaba: 							for (int _ = 0; _ < p3; ++_) ds.push_back(3);
d796dcebe4 2019-08-11        kinaba: 						}
d796dcebe4 2019-08-11        kinaba: 						else if (ds.empty() && p2 == 3 && p3 == 0) {
d796dcebe4 2019-08-11        kinaba: 							ds.push_back(2);
d796dcebe4 2019-08-11        kinaba: 							ds.push_back(4);
d796dcebe4 2019-08-11        kinaba: 						}
d796dcebe4 2019-08-11        kinaba: 						else {
d796dcebe4 2019-08-11        kinaba: 							for (; p2 >= 3; p2 -= 3) ds.push_back(8);
d796dcebe4 2019-08-11        kinaba: 							for (; p3 >= 2; p3 -= 2) ds.push_back(9);
d796dcebe4 2019-08-11        kinaba: 							if (p2 == 0) {
d796dcebe4 2019-08-11        kinaba: 								if (p3 == 0) {}
d796dcebe4 2019-08-11        kinaba: 								else if (p3 == 1) { ds.push_back(3); }
d796dcebe4 2019-08-11        kinaba: 							}
d796dcebe4 2019-08-11        kinaba: 							else if (p2 == 1) {
d796dcebe4 2019-08-11        kinaba: 								if (p3 == 0) { ds.push_back(2); }
d796dcebe4 2019-08-11        kinaba: 								else if (p3 == 1) { ds.push_back(6); }
d796dcebe4 2019-08-11        kinaba: 							}
d796dcebe4 2019-08-11        kinaba: 							else if (p2 == 2) {
d796dcebe4 2019-08-11        kinaba: 								if (p3 == 0) { ds.push_back(4);  }
d796dcebe4 2019-08-11        kinaba: 								else if (p3 == 1) { ds.push_back(2); ds.push_back(6); }
d796dcebe4 2019-08-11        kinaba: 							}
d796dcebe4 2019-08-11        kinaba: 						}
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: 						sort(ds.begin(), ds.end());
d796dcebe4 2019-08-11        kinaba: 						if (ds.size() <= 18) {
d796dcebe4 2019-08-11        kinaba: 							LL u = 0;
d796dcebe4 2019-08-11        kinaba: 							for (int d : ds)
d796dcebe4 2019-08-11        kinaba: 								u = u * 10 + d;
d796dcebe4 2019-08-11        kinaba: 							vs.push_back(u);
d796dcebe4 2019-08-11        kinaba: 						}
d796dcebe4 2019-08-11        kinaba: 					}
d796dcebe4 2019-08-11        kinaba: 				}
d796dcebe4 2019-08-11        kinaba: 		}
d796dcebe4 2019-08-11        kinaba: 		return *min_element(vs.begin(), vs.end());
d796dcebe4 2019-08-11        kinaba: 	}
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: 	int value(LL x, const vector<int>& base) {
d796dcebe4 2019-08-11        kinaba: 		if (x <= 9)
d796dcebe4 2019-08-11        kinaba: 			return base[int(x)];
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: 		LL p = 1;
d796dcebe4 2019-08-11        kinaba: 		for (; x; x /= 10)
d796dcebe4 2019-08-11        kinaba: 			p = p * (x % 10);
d796dcebe4 2019-08-11        kinaba: 		return value(p, base) + 1;
d796dcebe4 2019-08-11        kinaba: 	}
d796dcebe4 2019-08-11        kinaba: };
d796dcebe4 2019-08-11        kinaba: 
d796dcebe4 2019-08-11        kinaba: // BEGIN CUT HERE
d796dcebe4 2019-08-11        kinaba: #include <ctime>
d796dcebe4 2019-08-11        kinaba: double start_time; string timer()
d796dcebe4 2019-08-11        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
d796dcebe4 2019-08-11        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
d796dcebe4 2019-08-11        kinaba:  { os << "{ ";
d796dcebe4 2019-08-11        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
d796dcebe4 2019-08-11        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
d796dcebe4 2019-08-11        kinaba: void verify_case(const long long& Expected, const long long& Received) {
d796dcebe4 2019-08-11        kinaba:  bool ok = (Expected == Received);
d796dcebe4 2019-08-11        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
d796dcebe4 2019-08-11        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
d796dcebe4 2019-08-11        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
d796dcebe4 2019-08-11        kinaba: #define END	 verify_case(_, ReProduct().minimize(base, goal));}
d796dcebe4 2019-08-11        kinaba: int main(){
d796dcebe4 2019-08-11        kinaba: CASE(0)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = {0,1,1,1,1,1,1,1,1,1};
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 2;
d796dcebe4 2019-08-11        kinaba: 	long long _ = 11LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: CASE(1)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = {0,0,0,0,0,0,0,0,0,0};
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 3;
d796dcebe4 2019-08-11        kinaba: 	long long _ = 39LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: CASE(2)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = {2,0,0,0,0,0,0,0,0,0};
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 2;
d796dcebe4 2019-08-11        kinaba: 	long long _ = 0LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: CASE(3)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = {2,2,2,2,2,2,2,2,0,2};
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 1;
d796dcebe4 2019-08-11        kinaba: 	long long _ = 18LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: CASE(4)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = {2,1,2,2,1,1,1,0,1,0};
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 6;
d796dcebe4 2019-08-11        kinaba: 	long long _ = 268LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: CASE(5)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = { 2,1,2,2,1,1,1,0,1,0 };
d796dcebe4 2019-08-11        kinaba: 	vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = 11;
d796dcebe4 2019-08-11        kinaba: 	long long _ = -1LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: /*
d796dcebe4 2019-08-11        kinaba: CASE(6)
d796dcebe4 2019-08-11        kinaba: 	int base_[] = ;
d796dcebe4 2019-08-11        kinaba: 	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
d796dcebe4 2019-08-11        kinaba: 	int goal = ;
d796dcebe4 2019-08-11        kinaba: 	long long _ = LL;
d796dcebe4 2019-08-11        kinaba: END
d796dcebe4 2019-08-11        kinaba: */
d796dcebe4 2019-08-11        kinaba: }
d796dcebe4 2019-08-11        kinaba: // END CUT HERE