#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