4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<LL> vMul( const vector< vector<LL> >& A, const vector<LL>& B ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int n = A.size(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<LL> C(n); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<n; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<n; ++j) 4fd800b3a8 2011-02-23 kinaba: C[i] += A[i][j] * B[j]; 4fd800b3a8 2011-02-23 kinaba: return C; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int n = A.size(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > C(n, vector<LL>(n)); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<n; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<n; ++j) { 4fd800b3a8 2011-02-23 kinaba: LL Cij = 0; 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<n; ++k) 4fd800b3a8 2011-02-23 kinaba: Cij += A[i][k] * B[k][j]; 4fd800b3a8 2011-02-23 kinaba: C[i][j] = Cij; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return C; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > mPow( vector< vector<LL> > M, int t ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( t == 0 ) { 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > R(M.size(), vector<LL>(M.size())); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<R.size(); ++i) R[i][i] = 1; 4fd800b3a8 2011-02-23 kinaba: return R; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > R; 4fd800b3a8 2011-02-23 kinaba: for(; t; t>>=1, M=mMul(M,M)) 4fd800b3a8 2011-02-23 kinaba: if( t&1 ) 4fd800b3a8 2011-02-23 kinaba: R = (R.empty() ? M : mMul(R,M)); 4fd800b3a8 2011-02-23 kinaba: return R; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class ValidPlates 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: map<pair<int,int>, LL> memo; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string getPlate(vector <string> profane, int seqno) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // parse 4fd800b3a8 2011-02-23 kinaba: bool proh[10][10] = {}; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<profane.size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: stringstream sin(profane[i]); 4fd800b3a8 2011-02-23 kinaba: for(int n; sin>>n; ) 4fd800b3a8 2011-02-23 kinaba: proh[n/10][n%10] = true; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // matrix 4fd800b3a8 2011-02-23 kinaba: vector<LL> N(11, 1); N[10] = 0; 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > M(11, vector<LL>(11)); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<10; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<10; ++j) 4fd800b3a8 2011-02-23 kinaba: if( !proh[i][j] ) 4fd800b3a8 2011-02-23 kinaba: M[i][j] = 1; 4fd800b3a8 2011-02-23 kinaba: for(int j=1; j<11; ++j) 4fd800b3a8 2011-02-23 kinaba: M[10][j] = 1; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // binary search... 4fd800b3a8 2011-02-23 kinaba: LL L=-1, R=0; 4fd800b3a8 2011-02-23 kinaba: for(LL atprev=-1;; R=R*2+1) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > Mt = mPow(M, R); 4fd800b3a8 2011-02-23 kinaba: vector<LL> Nt = vMul(Mt, N); 4fd800b3a8 2011-02-23 kinaba: LL at = accumulate(Nt.begin()+1, Nt.end(), 0LL); 4fd800b3a8 2011-02-23 kinaba: if( atprev == at ) 4fd800b3a8 2011-02-23 kinaba: return ""; 4fd800b3a8 2011-02-23 kinaba: atprev = at; 4fd800b3a8 2011-02-23 kinaba: if( seqno <= at ) 4fd800b3a8 2011-02-23 kinaba: break; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: while(R-L>1) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: LL C=(L+R)/2; 4fd800b3a8 2011-02-23 kinaba: vector< vector<LL> > Mt = mPow(M, C); 4fd800b3a8 2011-02-23 kinaba: vector<LL> Nt = vMul(Mt, N); 4fd800b3a8 2011-02-23 kinaba: (seqno <= accumulate(Nt.begin()+1, Nt.end(), 0LL) ? R : L) = C; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: LL d = R+1; // #digits 4fd800b3a8 2011-02-23 kinaba: seqno -= vMul(mPow(M,R), N)[10]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string buf; 4fd800b3a8 2011-02-23 kinaba: int prev = -1; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<(d>50 ? 47 : d); ++i) 4fd800b3a8 2011-02-23 kinaba: if( prev == -1 ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector<LL> Nt = vMul(mPow(M, d-1-i), N); 4fd800b3a8 2011-02-23 kinaba: LL n = 0; 4fd800b3a8 2011-02-23 kinaba: for(int a=1; a<10; ++a) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: n += Nt[a]; 4fd800b3a8 2011-02-23 kinaba: if( seqno <= n ) 4fd800b3a8 2011-02-23 kinaba: {buf += char('0'+a); prev=a; seqno-=n-Nt[a]; break;} 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector<LL> Nt = vMul(mPow(M, d-1-i), N); 4fd800b3a8 2011-02-23 kinaba: LL n = 0; 4fd800b3a8 2011-02-23 kinaba: for(int a=0; a<10; ++a) if( !proh[prev][a] ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: n += Nt[a]; 4fd800b3a8 2011-02-23 kinaba: if( seqno <= n ) 4fd800b3a8 2011-02-23 kinaba: {buf += char('0'+a); prev=a; seqno-=n-Nt[a]; break;} 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return (d>50 ? buf+"..." : buf); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: 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(); } 4fd800b3a8 2011-02-23 kinaba: private: 4fd800b3a8 2011-02-23 kinaba: 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(); } 4fd800b3a8 2011-02-23 kinaba: 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; } } 4fd800b3a8 2011-02-23 kinaba: void test_case_0() { vector <string> Arg0; int Arg1 = 1000; string Arg2 = "1000"; verify_case(0, Arg2, getPlate(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: 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)); } 4fd800b3a8 2011-02-23 kinaba: 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)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_3() { string Arr0[] = {"00 01 02 03 04 05 06 07 08 09 11 12 13 14 15 16 17", 4fd800b3a8 2011-02-23 kinaba: "18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39", 4fd800b3a8 2011-02-23 kinaba: "44 45 46 47 48 49 55 56 57 58 59 66 67 68 69 77 78", 4fd800b3a8 2011-02-23 kinaba: "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)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_4() { string Arr0[] = {"00 01 02 03 04 05 07 08 09", 4fd800b3a8 2011-02-23 kinaba: "10 11 12 13 14 15 17 18 19", 4fd800b3a8 2011-02-23 kinaba: "20 21 22 24 25 26 27 28 29", 4fd800b3a8 2011-02-23 kinaba: "30 31 32 33 34 36 37 38 39", 4fd800b3a8 2011-02-23 kinaba: "41 43 45 46 48", 4fd800b3a8 2011-02-23 kinaba: "52 53 54 55 56 58 59", 4fd800b3a8 2011-02-23 kinaba: "60 61 63 64 66 67 68 69", 4fd800b3a8 2011-02-23 kinaba: "70 72 73 74 75 76 77 78", 4fd800b3a8 2011-02-23 kinaba: "80 81 82 83 84 86 87 88 89", 4fd800b3a8 2011-02-23 kinaba: "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)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_5() { string Arr0[] = {"00 01 02 03 04 05 06 07 08 09", 4fd800b3a8 2011-02-23 kinaba: "10 11 12 13 14 16 17 19", 4fd800b3a8 2011-02-23 kinaba: "20 21 22 23 24 25 26 27 28 29", 4fd800b3a8 2011-02-23 kinaba: "30 31 32 33 34 35 36 38 39", 4fd800b3a8 2011-02-23 kinaba: "41 42 43 44 45 46 49", 4fd800b3a8 2011-02-23 kinaba: "50 52 53 54 55 57 58 59", 4fd800b3a8 2011-02-23 kinaba: "60 61 62 63 64 65 66 67 68 69", 4fd800b3a8 2011-02-23 kinaba: "70 72 73 74 75 76 77 78 79", 4fd800b3a8 2011-02-23 kinaba: "80 81 82 83 84 85 86 87 88 89", 4fd800b3a8 2011-02-23 kinaba: "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)); } 4fd800b3a8 2011-02-23 kinaba: 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"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2000000000; string Arg2 = "11111111111111111111111111111111111111111111111..."; verify_case(6, Arg2, getPlate(Arg0, Arg1)); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: int main() { ValidPlates().run_test(-1); } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE