ADDED SRM/TCO13-3B-U/1A.cpp Index: SRM/TCO13-3B-U/1A.cpp ================================================================== --- SRM/TCO13-3B-U/1A.cpp +++ SRM/TCO13-3B-U/1A.cpp @@ -0,0 +1,160 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +const int ANY = 0; + +static const unsigned MODVAL = 1000000009; +struct mint +{ + unsigned val; + mint():val(0){} + mint(int x):val(x%MODVAL) {} + mint(unsigned x):val(x%MODVAL) {} + mint(LL x):val(x%MODVAL) {} +}; +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } +mint operator+(mint x, mint y) { return x+=y; } +mint operator-(mint x, mint y) { return x-=y; } +mint operator*(mint x, mint y) { return x*=y; } + +class SimilarSequences { public: + int count(vector seq, int bound) + { + vector< vector > cand; + cand.push_back(seq); + for(int i=0; i s = seq; + s.erase(s.begin() + i); + s.push_back(ANY); + cand.push_back(s); + for(int w=s.size()-1; w>0; --w) { + swap(s[w], s[w-1]); + cand.push_back(s); + } + } + vector idx; + for(int i=0; i >& cand, const vector& idx, int B) + { + if(idx.empty()) + return 0; + if(I == cand[0].size()) + return 1; + + mint total = 0; + + set head; + for(int k=0; k::iterator it=head.begin(); it!=head.end(); ++it) + { + int h = *it; + vector idx2; + for(int k=0; k head.size()) { + vector idx2; + for(int k=0; k +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(_, SimilarSequences().count(seq, bound));} +int main(){ + +CASE(0) + int seq_[] = {1, 1}; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = 3; + int _ = 5; +END +CASE(1) + int seq_[] = {1, 2}; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = 2; + int _ = 4; +END +CASE(2) + int seq_[] = {999999999}; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = 1000000000; + int _ = 1000000000; +END +CASE(3) + int seq_[] = {1, 2, 3, 4, 5}; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = 5; + int _ = 97; +END +CASE(4) + int seq_[] = {5, 8, 11, 12, 4, 1, 7, 9}; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = 1000000000; + int _ = 999999363; +END +/* +CASE(5) + int seq_[] = ; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = ; + int _ = ; +END +CASE(6) + int seq_[] = ; + vector seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); + int bound = ; + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO13-3B-U/1B.cpp Index: SRM/TCO13-3B-U/1B.cpp ================================================================== --- SRM/TCO13-3B-U/1B.cpp +++ SRM/TCO13-3B-U/1B.cpp @@ -0,0 +1,149 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +static const int INF = 999, UNK = -1; + +int bitcnt(int x) +{ + int c = 0; + for(; x; x>>=1) + c += x&1; + return c; +} + +class AntlerSwapping { public: + int getmin(vector a, vector b, int capacity) + { + int N = a.size(); + vector tbl(1< c; + for(int i=0; (1< capacity) + can = false; + tbl[mask] = can; + } + vector memo(1<=INF ? -1 : best; + } + + int rec(int mask, const vector& tbl, vector& memo) + { + if(memo[mask] != UNK) + return memo[mask]; + if(mask == 0) + return 0; + int best = INF; + for(int m2=mask; m2; m2=(m2-1)&mask) + { + int bc = bitcnt(m2); + if(tbl[m2]) + best = min(best, (bc-1) + rec(mask&~m2, tbl, memo)); + } + return memo[mask] = 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(_, AntlerSwapping().getmin(antler1, antler2, capacity));} +int main(){ + +CASE(0) + int antler1_[] = {3, 2, 2}; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = {3, 5, 5}; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = 0; + int _ = 1; +END +CASE(1) + int antler1_[] = {4, 2, 6, 4, 8, 5, 2, 3}; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = {3, 4, 5, 2, 8, 5, 7, 6}; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = 1; + int _ = 2; +END +CASE(2) + int antler1_[] = {12, 34, 56, 78}; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = {1234, 2345, 3456, 4567}; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = 100; + int _ = -1; +END +CASE(3) + int antler1_[] = {47, 58, 2013}; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = {49, 55, 2013}; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = 3; + int _ = 0; +END +CASE(4) + int antler1_[] = {4, 1, 7, 5, 7, 8, 2, 1, 3, 1, 7, 5, 9, 4, 9, 1}; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = {10, 6, 5, 3, 1, 8, 4, 4, 4, 7, 1, 4, 6, 5, 10, 10}; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = 1; + int _ = 7; +END +/* +CASE(5) + int antler1_[] = ; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = ; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = ; + int _ = ; +END +CASE(6) + int antler1_[] = ; + vector antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_)); + int antler2_[] = ; + vector antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_)); + int capacity = ; + int _ = ; +END +*/ +} +// END CUT HERE