ADDED SRM/TCO11-2-U/1A.cpp Index: SRM/TCO11-2-U/1A.cpp ================================================================== --- SRM/TCO11-2-U/1A.cpp +++ SRM/TCO11-2-U/1A.cpp @@ -0,0 +1,103 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +static const int MODVAL = 1000000007; + +class GuessTheNumberGame { public: + int possibleClues(int n) + { + vector isPrime(n+1, true); + vector ps; + for(LL p=2; p<=n; ++p) + if( isPrime[p] ) { + ps.push_back(p); + for(LL q=p*p; q<=n; q+=p) + isPrime[q] = false; + } + + LL cnt = 1; + for(int i=0; i +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& 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(_, GuessTheNumberGame().possibleClues(n));} +int main(){ + +CASE(0) + int n = 5; + int _ = 12; +END +CASE(1) + int n = 16; + int _ = 240; +END +CASE(2) + int n = 1; + int _ = 1; +END +CASE(3) + int n = 1000000; + int _ = 677298706; +END +CASE(4) + int n = 10000000; + int _ = -1; +END +CASE(5) + int n = 1; + int _ = 1; +END +CASE(6) + int n = 6; + int _ = 12; +END +CASE(7) + int n = 7; + int _ = 24; +END +CASE(8) + int n = 8; + int _ = 32; +END + +} +// END CUT HERE ADDED SRM/TCO11-2-U/1B-U.cpp Index: SRM/TCO11-2-U/1B-U.cpp ================================================================== --- SRM/TCO11-2-U/1B-U.cpp +++ SRM/TCO11-2-U/1B-U.cpp @@ -0,0 +1,146 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class STable { public: + string getString(string s, string t, long long pos) + { + const int S = s.size(); + const int T = t.size(); + vector< vector > len(S+1, vector(T+1)); + for(int i=1; i<=S; ++i) + len[i][0] = 1; + for(int k=1; k<=T; ++k) + len[0][k] = 1; + for(int i=1; i<=S; ++i) + for(int k=1; k<=T; ++k) + len[i][k] = len[i-1][k] + len[i][k-1]; + + string ans; + for(LL p=pos; p >& len, LL p, int i, int k) + { + if(i==0) + return t[k-1]; + if(k==0) + return s[i-1]; + + if( early(s, t, i-1, k, i, k-1) ) + if( p < len[i-1][k] ) + return theChar(s,t,len,p,i-1,k); + else + return theChar(s,t,len,p-len[i-1][k],i,k-1); + else + if( p < len[i][k-1] ) + return theChar(s,t,len,p,i,k-1); + else + return theChar(s,t,len,p-len[i][k-1],i-1,k); + } + + bool early(const string& s, const string & t, int i, int k, int ii, int kk) + { + string le,ri; + for(int x=0; x +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const string& Expected, const string& 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(_, STable().getString(s, t, pos));} +int main(){ + +CASE(0) + string s = "ad"; + string t = "cb"; + long long pos = 0LL; + string _ = "acbacd"; +END +CASE(1) + string s = "fox"; + string t = "cat"; + long long pos = 0LL; + string _ = "acfcfoacftacfcfocfox"; +END +CASE(2) + string s = "Ra6b1t"; + string t = "W0lf"; + long long pos = 66LL; + string _ = "RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6"; +END +CASE(3) + string s = "M0HAXG"; + string t = "COFU12"; + long long pos = 919LL; + string _ = "MOFU2"; +END +CASE(4) + string s = "a0B1c2D3e4F5gHiJkLmN"; + string t = "A9b8C7d6EfGhIjKlMn"; + long long pos = 9876543210LL; + string _ = "B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9"; +END +CASE(5) + string s = "TCOR2"; + string t = "MEDiUm"; + long long pos = 350LL; + string _ = "MTDEMTiCMTEMTDEMTDEMTiDEMTiUCMTEMTCMTOCMTEMTDEMTCM"; +END +CASE(6) + string s = "b"; + string t = "a"; + long long pos = 0LL; + string _ = "ab"; +END +CASE(6) + string s = "b"; + string t = "a"; + long long pos = 1LL; + string _ = "b"; +END +CASE(7) + string s = "01234abcdefghijklmnopqrstuvwxyz"; + string t = "56789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + long long pos = 999999999LL; + string _ = "??"; +END + +} +// END CUT HERE