ADDED SRM/TCO14-2B-U/1A.cpp Index: SRM/TCO14-2B-U/1A.cpp ================================================================== --- SRM/TCO14-2B-U/1A.cpp +++ SRM/TCO14-2B-U/1A.cpp @@ -0,0 +1,135 @@ +#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 SwitchingGame { public: + int timeToWin(vector states) + { + const int W = states[0].size(); + string cur(W, '-'); + + int sec = 0; + 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(_, SwitchingGame().timeToWin(states));} +int main(){ + +CASE(1) + string states_[] = {"+-++", + "+-++"}; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = 3; +END +CASE(0) + string states_[] = {"++--", + "--++"}; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = 5; +END +CASE(2) + string states_[] = {"++", + "+?", + "?+", + "++"}; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = 5; +END +CASE(3) + string states_[] = {"+", + "?", + "?", + "?", + "-"}; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = 7; +END +CASE(4) + string states_[] = {"+??+++", + "++??+-", + "?++??+", + "?-+-??", + "??+?++", + "++-?+?", + "?++?-+", + "?--+++", + "-??-?+"} +; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = 20; +END +/* +CASE(5) + string states_[] = ; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = ; +END +CASE(6) + string states_[] = ; + vector states(states_, states_+sizeof(states_)/sizeof(*states_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO14-2B-U/1B.cpp Index: SRM/TCO14-2B-U/1B.cpp ================================================================== --- SRM/TCO14-2B-U/1B.cpp +++ SRM/TCO14-2B-U/1B.cpp @@ -0,0 +1,100 @@ +#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 SumAndProductPuzzle { public: + long long getSum(int A, int B) + { + static const int N = 5000000; + vector isp(N+1, true); + for(int p=2; p<=N; ++p) + if(isp[p]) + for(int q=p+p; q<=N; q+=p) + isp[q] = false; + + vector has_dec(N+1, false); + for(int p=2; p<=N; ++p) + for(int S=p+p; S<=N; S+=p) { + int q = S/p; + if(!isp[p+q-1]) + has_dec[S] = true; + } + + LL sum = 0; + for(int S=A; S<=B; ++S) + if(!isp[S-1] && !has_dec[S-1]) + sum += S; + return sum; + } +}; + +// BEGIN CUT HERE +#include +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 long long& Expected, const long long& 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(_, SumAndProductPuzzle().getSum(A, B));} +int main(){ + +CASE(0) + int A = 30; + int B = 33; + long long _ = 33LL; +END +CASE(1) + int A = 8; + int B = 11; + long long _ = 19LL; +END +CASE(2) + int A = 40; + int B = 43; + long long _ = 0LL; +END +CASE(3) + int A = 47; + int B = 74; + long long _ = 168LL; +END +CASE(4) + int A = 1; + int B = 2; + long long _ = 0LL; +END +CASE(5) + int A = 1; + int B = 5000000; + long long _ = -1LL; +END +CASE(6) + int A = 1; + int B = 1; + long long _ = 0LL; +END +} +// END CUT HERE ADDED SRM/TCO14-2B-U/1C-U.cpp Index: SRM/TCO14-2B-U/1C-U.cpp ================================================================== --- SRM/TCO14-2B-U/1C-U.cpp +++ SRM/TCO14-2B-U/1C-U.cpp @@ -0,0 +1,136 @@ +#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 AlwaysDefined { public: + long long countIntegers(long long L, long long R, int W) + { + vector> tbl(W); + for(int q=1; q<=W-1; ++q) + for(int r=1; r<=W-1; ++r) + if(q*r%W == r) + tbl[q].push_back(r); + + // count all numbers that can be generated by repeating + // x ==> rx where tbl[x%W].has(r) + if(R<=1000000) + { + vector V(R+1, false); + for(int k=0; k*W+1<=R; ++k) + { + queue Q; + if(!V[k*W+1]) + Q.push(k*W+1), V[k*W+1]=true; + while(!Q.empty()) + { + int s = Q.front(); + Q.pop(); + for(int r: tbl[s%W]) { + if(s*r<=R && !V[s*r]) + Q.push(s*r), V[s*r]=true; + } + } + } + LL cnt = 0; + for(LL X=L; X<=R; ++X) + if(V[X]) + ++cnt; + return cnt; + } + + + LL cnt = 0; + for(LL X=L; X<=R; ++X) + { + LL x = X; + for(;;) { + if(x%W==0) + break; + if(x%W==1) + {++cnt; break;} + if(x%(x%W)!=0) + break; + x /= x%W; + } + } + return cnt; + } +}; + +// BEGIN CUT HERE +#include +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 long long& Expected, const long long& 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(_, AlwaysDefined().countIntegers(L, R, W));} +int main(){ + +CASE(0) + long long L = 10LL; + long long R = 10LL; + int W = 4; + long long _ = 1LL; +END +CASE(1) + long long L = 1LL; + long long R = 99LL; + int W = 2; + long long _ = 50LL; +END +CASE(2) + long long L = 1282LL; + long long R = 1410LL; + int W = 10; + long long _ = 42LL; +END +CASE(178116) + long long L = 1LL; + long long R = 1000000LL; + int W = 30; + long long _ = 154161LL; +END +CASE(3) + long long L = 29195807LL; + long long R = 273209804877LL; + int W = 42; + long long _ = 31415926535LL; +END +CASE(4) + long long L = 1LL; + long long R = 1000000000000000000LL; + int W = 3000; + long long _ = -1LL; +END +CASE(5) + long long L = 1LL; + long long R = 1000000000000000000LL; + int W = 3; + long long _ = -1LL; +END +} +// END CUT HERE