46d6ab9496 2011-12-07        kinaba: #include <iostream>
46d6ab9496 2011-12-07        kinaba: #include <sstream>
46d6ab9496 2011-12-07        kinaba: #include <iomanip>
46d6ab9496 2011-12-07        kinaba: #include <vector>
46d6ab9496 2011-12-07        kinaba: #include <string>
46d6ab9496 2011-12-07        kinaba: #include <map>
46d6ab9496 2011-12-07        kinaba: #include <set>
46d6ab9496 2011-12-07        kinaba: #include <algorithm>
46d6ab9496 2011-12-07        kinaba: #include <numeric>
46d6ab9496 2011-12-07        kinaba: #include <iterator>
46d6ab9496 2011-12-07        kinaba: #include <functional>
46d6ab9496 2011-12-07        kinaba: #include <complex>
46d6ab9496 2011-12-07        kinaba: #include <queue>
46d6ab9496 2011-12-07        kinaba: #include <stack>
46d6ab9496 2011-12-07        kinaba: #include <cmath>
46d6ab9496 2011-12-07        kinaba: #include <cassert>
46d6ab9496 2011-12-07        kinaba: #include <cstring>
46d6ab9496 2011-12-07        kinaba: #ifdef __GNUC__
46d6ab9496 2011-12-07        kinaba: #include <ext/hash_map>
46d6ab9496 2011-12-07        kinaba: #define unordered_map __gnu_cxx::hash_map
46d6ab9496 2011-12-07        kinaba: #else
46d6ab9496 2011-12-07        kinaba: #include <unordered_map>
46d6ab9496 2011-12-07        kinaba: #endif
46d6ab9496 2011-12-07        kinaba: using namespace std;
46d6ab9496 2011-12-07        kinaba: typedef long long LL;
46d6ab9496 2011-12-07        kinaba: typedef complex<double> CMP;
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: class MultiplesWithLimit { public:
46d6ab9496 2011-12-07        kinaba: 	string minMultiples(int N, vector <int> forbiddenDigits)
46d6ab9496 2011-12-07        kinaba: 	{
46d6ab9496 2011-12-07        kinaba: 		vector<int> allowed;
46d6ab9496 2011-12-07        kinaba: 		for(int i=0; i<=9; ++i)
46d6ab9496 2011-12-07        kinaba: 			if( find(forbiddenDigits.begin(), forbiddenDigits.end(), i) == forbiddenDigits.end() )
46d6ab9496 2011-12-07        kinaba: 				allowed.push_back(i);
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 		vector< vector< pair<char,int> > > G(N);
46d6ab9496 2011-12-07        kinaba: 		for(int v=0; v<N; ++v)
46d6ab9496 2011-12-07        kinaba: 			for(int k=0; k<allowed.size(); ++k)
46d6ab9496 2011-12-07        kinaba: 				G[v].push_back( make_pair(char('0'+allowed[k]), (v*10 + allowed[k])%N) );
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 		vector<int> dist_to_zero(N, INF);
46d6ab9496 2011-12-07        kinaba: 		queue<int> Q;
46d6ab9496 2011-12-07        kinaba: 		dist_to_zero[0] = 0;
46d6ab9496 2011-12-07        kinaba: 		Q.push(0);
46d6ab9496 2011-12-07        kinaba: 		while( !Q.empty() )
46d6ab9496 2011-12-07        kinaba: 		{
46d6ab9496 2011-12-07        kinaba: 			int v = Q.front();
46d6ab9496 2011-12-07        kinaba: 			Q.pop();
46d6ab9496 2011-12-07        kinaba: 			for(int i=0; i<allowed.size(); ++i)
46d6ab9496 2011-12-07        kinaba: 			{
46d6ab9496 2011-12-07        kinaba: 				int vv = (allowed[i]*POW(10,dist_to_zero[v],N) + v) % N;
46d6ab9496 2011-12-07        kinaba: 				if( dist_to_zero[vv] == INF ) {
46d6ab9496 2011-12-07        kinaba: 					dist_to_zero[vv] = dist_to_zero[v] + 1;
46d6ab9496 2011-12-07        kinaba: 					Q.push(vv);
46d6ab9496 2011-12-07        kinaba: 				}
46d6ab9496 2011-12-07        kinaba: 			}
46d6ab9496 2011-12-07        kinaba: 		}
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 		string all;
46d6ab9496 2011-12-07        kinaba: 		int v = 0;
46d6ab9496 2011-12-07        kinaba: 		do {
46d6ab9496 2011-12-07        kinaba: 			int best = INF;
46d6ab9496 2011-12-07        kinaba: 			int besta = -1;
46d6ab9496 2011-12-07        kinaba: 			for(int i=0; i<allowed.size(); ++i)
46d6ab9496 2011-12-07        kinaba: 				if(v>0 || allowed[i]>0)
46d6ab9496 2011-12-07        kinaba: 				{
46d6ab9496 2011-12-07        kinaba: 					int vv = (v*10 + allowed[i]) % N;
46d6ab9496 2011-12-07        kinaba: 					if( dist_to_zero[vv] < best ) {
46d6ab9496 2011-12-07        kinaba: 						best = dist_to_zero[vv];
46d6ab9496 2011-12-07        kinaba: 						besta = allowed[i];
46d6ab9496 2011-12-07        kinaba: 					}
46d6ab9496 2011-12-07        kinaba: 				}
46d6ab9496 2011-12-07        kinaba: 			if( best == INF )
46d6ab9496 2011-12-07        kinaba: 				return "IMPOSSIBLE";
46d6ab9496 2011-12-07        kinaba: 			all += char('0' + besta);
46d6ab9496 2011-12-07        kinaba: 			v = (v*10 + besta) % N;
46d6ab9496 2011-12-07        kinaba: 			cerr << v << " " << dist_to_zero[v] << " " << besta << endl;
46d6ab9496 2011-12-07        kinaba: 		} while( v );
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 		if( all.size() <= 8 )
46d6ab9496 2011-12-07        kinaba: 			return all;
46d6ab9496 2011-12-07        kinaba: 		else {
46d6ab9496 2011-12-07        kinaba: 			stringstream ss;
46d6ab9496 2011-12-07        kinaba: 			ss << all.substr(0,3) << "..." << all.substr(all.size()-3) << "(" << all.size() << " digits)";
46d6ab9496 2011-12-07        kinaba: 			return ss.str();
46d6ab9496 2011-12-07        kinaba: 		}
46d6ab9496 2011-12-07        kinaba: 	}
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 	int POW(int v, int e, int m)
46d6ab9496 2011-12-07        kinaba: 	{
46d6ab9496 2011-12-07        kinaba: 		int r = 1%m;
46d6ab9496 2011-12-07        kinaba: 		for(; e; e>>=1,v=v*v%m)
46d6ab9496 2011-12-07        kinaba: 			if( e&1 )
46d6ab9496 2011-12-07        kinaba: 				r = r*v%m;
46d6ab9496 2011-12-07        kinaba: 		return r;
46d6ab9496 2011-12-07        kinaba: 	}
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: 	static const int INF = 0x1fffffff;
46d6ab9496 2011-12-07        kinaba: };
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: // BEGIN CUT HERE
46d6ab9496 2011-12-07        kinaba: #include <ctime>
46d6ab9496 2011-12-07        kinaba: double start_time; string timer()
46d6ab9496 2011-12-07        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
46d6ab9496 2011-12-07        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
46d6ab9496 2011-12-07        kinaba:  { os << "{ ";
46d6ab9496 2011-12-07        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
46d6ab9496 2011-12-07        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
46d6ab9496 2011-12-07        kinaba: void verify_case(const string& Expected, const string& Received) {
46d6ab9496 2011-12-07        kinaba:  bool ok = (Expected == Received);
46d6ab9496 2011-12-07        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
46d6ab9496 2011-12-07        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
46d6ab9496 2011-12-07        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
46d6ab9496 2011-12-07        kinaba: #define END	 verify_case(_, MultiplesWithLimit().minMultiples(N, forbiddenDigits));}
46d6ab9496 2011-12-07        kinaba: int main(){
46d6ab9496 2011-12-07        kinaba: 
46d6ab9496 2011-12-07        kinaba: CASE(0)
46d6ab9496 2011-12-07        kinaba: 	int N = 8;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = {2,3,4,5,6,7,8,9};
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = "1000";
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: CASE(1)
46d6ab9496 2011-12-07        kinaba: 	int N = 9;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = {1,3,4,5,6,7,8,9};
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = "222...222(9 digits)";
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: CASE(2)
46d6ab9496 2011-12-07        kinaba: 	int N = 524;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = {5,2,4};
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = "3668";
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: CASE(3)
46d6ab9496 2011-12-07        kinaba: 	int N = 10000;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = {0};
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = "IMPOSSIBLE";
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: CASE(4)
46d6ab9496 2011-12-07        kinaba: 	int N = 1;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = {0,1,2,3,4,5,6,7,8,9};
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = "IMPOSSIBLE";
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: /*
46d6ab9496 2011-12-07        kinaba: CASE(5)
46d6ab9496 2011-12-07        kinaba: 	int N = ;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = ;
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = ;
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: CASE(6)
46d6ab9496 2011-12-07        kinaba: 	int N = ;
46d6ab9496 2011-12-07        kinaba: 	int forbiddenDigits_[] = ;
46d6ab9496 2011-12-07        kinaba: 	  vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
46d6ab9496 2011-12-07        kinaba: 	string _ = ;
46d6ab9496 2011-12-07        kinaba: END
46d6ab9496 2011-12-07        kinaba: */
46d6ab9496 2011-12-07        kinaba: }
46d6ab9496 2011-12-07        kinaba: // END CUT HERE