Artifact Content
Not logged in

Artifact 655c27d7a69723ce8a77cc3f0be67011b331fa1a


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;

vector<LL> vMul( const vector< vector<LL> >& A, const vector<LL>& B )
{
	const int n = A.size();

	vector<LL> C(n);
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			C[i] += A[i][j] * B[j];
	return C;
}

vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
{
	const int n = A.size();

	vector< vector<LL> > C(n, vector<LL>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j) {
			LL Cij = 0;
			for(int k=0; k<n; ++k)
				Cij += A[i][k] * B[k][j];
			C[i][j] = Cij;
		}
	return C;
}

vector< vector<LL> > mPow( vector< vector<LL> > M, int t )
{
	if( t == 0 ) {
		vector< vector<LL> > R(M.size(), vector<LL>(M.size()));
		for(int i=0; i<R.size(); ++i) R[i][i] = 1;
		return R;
	}
	vector< vector<LL> > R;
	for(; t; t>>=1, M=mMul(M,M))
		if( t&1 )
			R = (R.empty() ? M : mMul(R,M));
	return R;
}

class ValidPlates
{
public:
	map<pair<int,int>, LL> memo;

	string getPlate(vector <string> profane, int seqno) 
	{
		// parse
		bool proh[10][10] = {};
		for(int i=0; i<profane.size(); ++i) {
			stringstream sin(profane[i]);
			for(int n; sin>>n; )
				proh[n/10][n%10] = true;
		}

		// matrix
		vector<LL> N(11, 1); N[10] = 0;
		vector< vector<LL> > M(11, vector<LL>(11));
		for(int i=0; i<10; ++i)
		for(int j=0; j<10; ++j)
			if( !proh[i][j] )
				M[i][j] = 1;
		for(int j=1; j<11; ++j)
			M[10][j] = 1;

		// binary search...
		LL L=-1, R=0;
		for(LL atprev=-1;; R=R*2+1)
		{
			vector< vector<LL> > Mt = mPow(M,  R);
			vector<LL>           Nt = vMul(Mt, N);
			LL                   at = accumulate(Nt.begin()+1, Nt.end(), 0LL);
			if( atprev == at )
				return "";
			atprev = at;
			if( seqno <= at )
				break;
		}
		while(R-L>1)
		{
			LL C=(L+R)/2;
			vector< vector<LL> > Mt = mPow(M, C);
			vector<LL>           Nt = vMul(Mt, N);
			(seqno <= accumulate(Nt.begin()+1, Nt.end(), 0LL) ? R : L) = C;
		}
		LL d = R+1; // #digits
		seqno -= vMul(mPow(M,R), N)[10];

		string buf;
		int prev = -1;
		for(int i=0; i<(d>50 ? 47 : d); ++i)
			if( prev == -1 )
			{
				vector<LL> Nt = vMul(mPow(M, d-1-i), N);
				LL n = 0;
				for(int a=1; a<10; ++a)
				{
					n += Nt[a];
					if( seqno <= n )
						{buf += char('0'+a); prev=a; seqno-=n-Nt[a]; break;}
				}
			}
			else
			{
				vector<LL> Nt = vMul(mPow(M, d-1-i), N);
				LL n = 0;
				for(int a=0; a<10; ++a) if( !proh[prev][a] )
				{
					n += Nt[a];
					if( seqno <= n )
						{buf += char('0'+a); prev=a; seqno-=n-Nt[a]; break;}
				}
			}
		return (d>50 ? buf+"..." : buf);
	}

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { vector <string> Arg0; int Arg1 = 1000; string Arg2 = "1000"; verify_case(0, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_1() { string Arr0[] = {"10"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 10; string Arg2 = "11"; verify_case(1, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_2() { string Arr0[] = {"10"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2000000000; string Arg2 = "2277659869"; verify_case(2, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_3() { string Arr0[] = {"00 01 02 03 04 05 06 07 08 09 11 12 13 14 15 16 17",
 "18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39",
 "44 45 46 47 48 49 55 56 57 58 59 66 67 68 69 77 78",
 "79 88 89 99 99 99 99 99"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1023; string Arg2 = ""; verify_case(3, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_4() { string Arr0[] = {"00 01 02 03 04 05 07 08 09",
 "10 11 12 13 14 15 17 18 19",
 "20 21 22 24 25 26 27 28 29",
 "30 31 32 33 34 36 37 38 39",
 "41 43 45 46 48",
 "52 53 54 55 56 58 59",
 "60 61 63 64 66 67 68 69",
 "70 72 73 74 75 76 77 78",
 "80 81 82 83 84 86 87 88 89",
 "90 91 92 94 95 96 97 98"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2000000000; string Arg2 = "79999999351623516571657999935799993"; verify_case(4, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_5() { string Arr0[] = {"00 01 02 03 04 05 06 07 08 09",
 "10 11 12 13 14 16 17 19",
 "20 21 22 23 24 25 26 27 28 29",
 "30 31 32 33 34 35 36 38 39",
 "41 42 43 44 45 46 49",
 "50 52 53 54 55 57 58 59",
 "60 61 62 63 64 65 66 67 68 69",
 "70 72 73 74 75 76 77 78 79",
 "80 81 82 83 84 85 86 87 88 89",
 "90 91 92 93 94 95 98 99"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2000000000; string Arg2 = "37151515151515151515151515151515151515151515151..."; verify_case(5, Arg2, getPlate(Arg0, Arg1)); }
	void test_case_6() { string Arr0[] = {"00 01 02 03 04 05 06 07 08 09", "10 12 13 14 15 16 17 18 19", "20 21 22 23 24 25 26 27 28 29", "30 31 32 33 34 35 36 37 38 39", "40 41 42 43 44 45 46 47 48 49", "50 51 52 53 54 55 56 57 58 59", "60 61 62 63 64 65 66 67 68 69", "70 71 72 73 74 75 76 77 78 79", "80 81 82 83 84 85 86 87 88 89", "90 91 92 93 94 95 96 97 98 99"};
 vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2000000000; string Arg2 = "11111111111111111111111111111111111111111111111..."; verify_case(6, Arg2, getPlate(Arg0, Arg1)); }

// END CUT HERE
};
// BEGIN CUT HERE 
int main() { ValidPlates().run_test(-1); }
// END CUT HERE