Artifact Content
Not logged in

Artifact ed3910ded0d2a5171b844c92871a2996d43fd8ce


#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 <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class ReProduct { public:
	long long minimize(vector <int> base, int goal)
	{
		vector<tuple<LL,int,int,int,int>> cand(1, make_tuple(0LL,-1,-1,-1,-1));
		for (LL a = 1,ai=0; a <= 1000000000000000000LL; a *= 2,++ai)
			for (LL b = a,bi=0; b <= 1000000000000000000LL; b *= 3,++bi)
				for (LL c = b,ci=0; c <= 1000000000000000000LL; c *= 5,++ci)
					for (LL d = c,di=0; d <= 1000000000000000000LL; d *= 7,++di)
						cand.emplace_back(d, ai,bi,ci,di);

		vector<LL> vs;
		for (auto cc : cand) {
			LL c = get<0>(cc);
			LL v = value(c, base);
			if (v == goal)
				vs.push_back(c);
			if (v + 1 == goal)
				if (c == 0)
					vs.push_back(10);
				else if (c==1)
					vs.push_back(11);
				else {
					int p2 = get<1>(cc);
					int p3 = get<2>(cc);
					int p5 = get<3>(cc);
					int p7 = get<4>(cc);
					if (p2 + p3 + p5 + p7 >= 2) {
						vector<int> ds;
						for (int _ = 0; _ < p5; ++_) ds.push_back(5);
						for (int _ = 0; _ < p7; ++_) ds.push_back(7);
						if (ds.empty() && p2 + p3 == 2) {
							for (int _ = 0; _ < p2; ++_) ds.push_back(2);
							for (int _ = 0; _ < p3; ++_) ds.push_back(3);
						}
						else if (ds.empty() && p2 == 3 && p3 == 0) {
							ds.push_back(2);
							ds.push_back(4);
						}
						else {
							for (; p2 >= 3; p2 -= 3) ds.push_back(8);
							for (; p3 >= 2; p3 -= 2) ds.push_back(9);
							if (p2 == 0) {
								if (p3 == 0) {}
								else if (p3 == 1) { ds.push_back(3); }
							}
							else if (p2 == 1) {
								if (p3 == 0) { ds.push_back(2); }
								else if (p3 == 1) { ds.push_back(6); }
							}
							else if (p2 == 2) {
								if (p3 == 0) { ds.push_back(4);  }
								else if (p3 == 1) { ds.push_back(2); ds.push_back(6); }
							}
						}

						sort(ds.begin(), ds.end());
						if (ds.size() <= 18) {
							LL u = 0;
							for (int d : ds)
								u = u * 10 + d;
							vs.push_back(u);
						}
					}
				}
		}
		return *min_element(vs.begin(), vs.end());
	}

	int value(LL x, const vector<int>& base) {
		if (x <= 9)
			return base[int(x)];

		LL p = 1;
		for (; x; x /= 10)
			p = p * (x % 10);
		return value(p, base) + 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 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(_, ReProduct().minimize(base, goal));}
int main(){
CASE(0)
	int base_[] = {0,1,1,1,1,1,1,1,1,1};
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = 2; 
	long long _ = 11LL; 
END
CASE(1)
	int base_[] = {0,0,0,0,0,0,0,0,0,0};
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = 3; 
	long long _ = 39LL; 
END
CASE(2)
	int base_[] = {2,0,0,0,0,0,0,0,0,0};
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = 2; 
	long long _ = 0LL; 
END
CASE(3)
	int base_[] = {2,2,2,2,2,2,2,2,0,2};
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = 1; 
	long long _ = 18LL; 
END
CASE(4)
	int base_[] = {2,1,2,2,1,1,1,0,1,0};
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = 6; 
	long long _ = 268LL; 
END
CASE(5)
	int base_[] = { 2,1,2,2,1,1,1,0,1,0 };
	vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_));
	int goal = 11; 
	long long _ = -1LL; 
END
/*
CASE(6)
	int base_[] = ;
	  vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); 
	int goal = ; 
	long long _ = LL; 
END
*/
}
// END CUT HERE