ADDED SRM/630-U/1A.cpp Index: SRM/630-U/1A.cpp ================================================================== --- SRM/630-U/1A.cpp +++ SRM/630-U/1A.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 Egalitarianism3 { public: + int maxCities(int n, vector a, vector b, vector len) + { + if(n<=2) + return n; + + const int INF = 0x3fffffff; + vector> d(n, vector(n, INF)); + for(int i=0; i> cand; + for(int v=0; v(best, cand[rad].size()); + } + } + } + return best; + } +}; + +// 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 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(_, Egalitarianism3().maxCities(n, a, b, len));} +int main(){ + +CASE(0) + int n = 4; + int a_[] = {1,1,1}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {2,3,4}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int len_[] = {1,1,1}; + vector len(len_, len_+sizeof(len_)/sizeof(*len_)); + int _ = 3; +END +CASE(1) + int n = 6; + int a_[] = {1,2,3,2,3}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {2,3,4,5,6}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int len_[] = {2,1,3,2,3}; + vector len(len_, len_+sizeof(len_)/sizeof(*len_)); + int _ = 3; +END +CASE(2) + int n = 10; + int a_[] = {1,1,1,1,1,1,1,1,1}; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = {2,3,4,5,6,7,8,9,10}; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int len_[] = {1000,1000,1000,1000,1000,1000,1000,1000,1000}; + vector len(len_, len_+sizeof(len_)/sizeof(*len_)); + int _ = 9; +END +CASE(3) + int n = 1; + vector a; + vector b; + vector len; + int _ = 1; +END +/* +CASE(4) + int n = ; + int a_[] = ; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int len_[] = ; + vector len(len_, len_+sizeof(len_)/sizeof(*len_)); + int _ = ; +END +CASE(5) + int n = ; + int a_[] = ; + vector a(a_, a_+sizeof(a_)/sizeof(*a_)); + int b_[] = ; + vector b(b_, b_+sizeof(b_)/sizeof(*b_)); + int len_[] = ; + vector len(len_, len_+sizeof(len_)/sizeof(*len_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/630-U/1B.cpp Index: SRM/630-U/1B.cpp ================================================================== --- SRM/630-U/1B.cpp +++ SRM/630-U/1B.cpp @@ -0,0 +1,97 @@ +#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 SuffixArrayDiv1 { public: + int minimalCharacters(vector SA) + { + int N = SA.size(); + + vector rank(N); + for(int i=0; i rank[q+1]) + ++cnt; + } + 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 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(_, SuffixArrayDiv1().minimalCharacters(SA));} +int main(){ + +CASE(0) + int SA_[] = {3,0,1,2}; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = 2; +END +CASE(1) + int SA_[] = {3,2,1,0}; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = 1; +END +CASE(2) + int SA_[] = {0,1,2,3}; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = 2; +END +CASE(3) + int SA_[] = {7,4,8,6,1,5,2,9,3,0}; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = 4; +END +CASE(4) + int SA_[] = {0}; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = 1; +END +/* +CASE(5) + int SA_[] = ; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = ; +END +CASE(6) + int SA_[] = ; + vector SA(SA_, SA_+sizeof(SA_)/sizeof(*SA_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/630-U/1C-U.cpp Index: SRM/630-U/1C-U.cpp ================================================================== --- SRM/630-U/1C-U.cpp +++ SRM/630-U/1C-U.cpp @@ -0,0 +1,327 @@ +#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 NeverAskHerAge { public: + vector possibleSolution(int n, vector id1, vector id2, vector op, vector rl, vector val) + { + // !!!Being a geek, Jiro has to perfer 0-origin numbering!!! + for(auto& g: id1) --g; + for(auto& g: id2) --g; + + for(auto& s: rl) {if(s=="<=") s="L"; if(s==">=") s="G";} + + // check obviously false conditions. + for(int i=0; i(); + continue; + } + if(val[i]%1000 != 0) + return vector(); + int v = val[i] / 1000; + if(op[i]=="+" && (v<2 || v>200)) return vector(); + if(op[i]=="-" && (v<-99 || v>99)) return vector(); + if(op[i]=="*") { + if(v<1 || 10000(); + for(int p=2; p*p<=v; ++p) + while(v%p==0)v/=p; + if(v>100) return vector(); + } + } + + // Relevant constraints + vector> rel(n); + for(int i=0; i girls; for(int g=0; grel[g2].size();}); + + const int UNDETERMINED = 0; + vector x(n, UNDETERMINED); + function rec; + rec = [&](int gi){ + if(gi == n) + return true; + int g = girls[gi]; + for(int age=1; age<=100; ++age) + { + x[g] = age; + bool bad = false; + for(int i: rel[g]) if(x[id1[i]]!=UNDETERMINED && x[id2[i]]!=UNDETERMINED) { + if(!ok(x[id1[i]], op[i][0], x[id2[i]], rl[i][0], val[i])) + {bad=true; break;} + } else { + if(!ok_part(x[id1[i]], op[i][0], x[id2[i]], rl[i][0], val[i])) + {bad=true; break;} + } + if(!bad && rec(gi+1)) + return true; + x[g] = UNDETERMINED; + } + return false; + }; + if(!rec(0)) return vector(); + return x; + } + + static bool ok(int x1, char op, int x2, char rl, int val) + { + switch(op) { + case '+': return ok((x1+x2)*1000, rl, val); + case '-': return ok((x1-x2)*1000, rl, val); + case '*': return ok((x1*x2)*1000, rl, val); + case '/': return ok((x1)*1000, rl, val*x2); + } + return false; + } + static bool ok(int x, char rel, int y) + { + if(rel=='<') return x < y; + if(rel=='L') return x <= y; + if(rel=='>') return x > y; + if(rel=='G') return x >= y; + if(rel=='=') return x == y; + return false; + } + static bool ok_part(int x1, char op, int x2, char rl, int val) + { + switch(op) { + case '+': return ok_part_plus(max(x1,x2), rl, val); + case '-': return x1 ? ok_part_minusl(x1, rl, val) + : ok_part_minusr(x2, rl, val); + case '*': return ok_part_mult(max(x1,x2), rl, val); + case '/': return x1 ? ok_part_divl(x1, rl, val) + : ok_part_divr(x2, rl, val); + } + return true; + } + // (x + ?)*1000 rel y + static bool ok_part_plus(int x, char rel, int y) + { + if(rel=='<') return (x+1)*1000 < y; + if(rel=='L') return (x+1)*1000 <= y; + if(rel=='>') return (x+100)*1000 > y; + if(rel=='G') return (x+100)*1000 >= y; + if(rel=='=') return (x+1)*1000<=y && y<=(x+100)*1000; + return false; + } + // (x - ?)*1000 rel y + static bool ok_part_minusl(int x, char rel, int y) + { + if(rel=='<') return (x-100)*1000 < y; + if(rel=='L') return (x-100)*1000 <= y; + if(rel=='>') return (x-1)*1000 > y; + if(rel=='G') return (x-1)*1000 >= y; + if(rel=='=') return (x-100)*1000<=y && y<=(x-1)*1000; + return false; + } + // (? - x)*1000 rel y + static bool ok_part_minusr(int x, char rel, int y) + { + if(rel=='<') return (1-x)*1000 < y; + if(rel=='L') return (1-x)*1000 <= y; + if(rel=='>') return (100-x)*1000 > y; + if(rel=='G') return (100-x)*1000 >= y; + if(rel=='=') return (1-x)*1000<=y && y<=(100-x)*1000; + return false; + } + // (x * ?)*1000 rel y + static bool ok_part_mult(int x, char rel, int y) + { + if(rel=='<') return (x*1)*1000 < y; + if(rel=='L') return (x*1)*1000 <= y; + if(rel=='>') return (x*100)*1000 > y; + if(rel=='G') return (x*100)*1000 >= y; + if(rel=='=') return (x*1)*1000<=y && y<=(x*100)*1000 && y%(x*1000)==0; + return false; + } + // (x / ?)*1000 rel y + static bool ok_part_divl(int x, char rel, int y) + { + if(rel=='<') return x*1000 < y*100; + if(rel=='L') return x*1000 <= y*100; + if(rel=='>') return x*1000 > y*1; + if(rel=='G') return x*1000 >= y*1; + if(rel=='=') return x*1000 <= y*100 && x*1000 >= y*1 && (x*1000%y==0); + return false; + } + static bool ok_part_divr(int x, char rel, int y) + { + return true; + } +}; + +// 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 vector & Expected, const vector & 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(_, NeverAskHerAge().possibleSolution(n, id1, id2, op, rl, val));} +int main(){ + +CASE(0) + int n = 2; + int id1_[] = {1,1}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,2}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"+","*"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {"=","="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {10000,21000}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = {3, 7 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int n = 7; + int id1_[] = {1,2,3,4,5,6}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,3,4,5,6,7}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"/","/","/","/","/","/"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {"=","=","=","=","=","="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {2000,2000,2000,2000,2000,2000}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = {64, 32, 16, 8, 4, 2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int n = 2; + int id1_[] = {1,1}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,2}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"/","/"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {">","<"}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {2621,2622}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = {97, 37 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + int n = 2; + int id1_[] = {1,1}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,2}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"*","+"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {">","<="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {6000,5000}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + vector _; +END +CASE(4) + int n = 8; + int id1_[] = {1,3,5,7}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,4,6,8}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"+","-","*","/"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {">=","<=","=","<="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {200000,-99000,3589000,10}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = {100, 100, 1, 100, 97, 37, 1, 100 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int n = 8; + int id1_[] = {7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {"<","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {47636,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = {56, 77, 19, 59, 77, 87, 43, 51 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + int n = 8; + int id1_[] = {7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8}; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = {2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3}; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = {"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"}; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = {"=","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="}; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = {2000,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484}; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + vector _; +END +/* +CASE(7) + int n = ; + int id1_[] = ; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = ; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = ; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = ; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = ; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(8) + int n = ; + int id1_[] = ; + vector id1(id1_, id1_+sizeof(id1_)/sizeof(*id1_)); + int id2_[] = ; + vector id2(id2_, id2_+sizeof(id2_)/sizeof(*id2_)); + string op_[] = ; + vector op(op_, op_+sizeof(op_)/sizeof(*op_)); + string rl_[] = ; + vector rl(rl_, rl_+sizeof(rl_)/sizeof(*rl_)); + int val_[] = ; + vector val(val_, val_+sizeof(val_)/sizeof(*val_)); + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE