ADDED SRM/TCO15-2B-U/1A.cpp Index: SRM/TCO15-2B-U/1A.cpp ================================================================== --- SRM/TCO15-2B-U/1A.cpp +++ SRM/TCO15-2B-U/1A.cpp @@ -0,0 +1,86 @@ +#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 Bitwisdom { public: + double expectedActions(vector p) + { + double e = 0; + for(int i=1; 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 double& Expected, const double& Received) { + bool ok = (abs(Expected - Received) < 1e-9); + 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(_, Bitwisdom().expectedActions(p));} +int main(){ + +CASE(0) + int p_[] = {100, 100, 100}; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = 1.0; +END +CASE(1) + int p_[] = {50, 50}; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = 0.75; +END +CASE(2) + int p_[] = {0, 40, 50, 60}; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = 1.4; +END +CASE(3) + int p_[] = {37, 63, 23, 94, 12}; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = 2.6820475464; +END +/* +CASE(4) + int p_[] = ; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = ; +END +CASE(5) + int p_[] = ; + vector p(p_, p_+sizeof(p_)/sizeof(*p_)); + double _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO15-2B-U/1B.cpp Index: SRM/TCO15-2B-U/1B.cpp ================================================================== --- SRM/TCO15-2B-U/1B.cpp +++ SRM/TCO15-2B-U/1B.cpp @@ -0,0 +1,204 @@ +#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 Balance { public: + string canTransform(vector initial, vector target) + { + auto ti = gen_tree(initial); + auto tt = gen_tree(target); + return tree_eq(ti, tt) ? "Possible" : "Impossible"; + } + + vector> gen_tree(vector s) { + s.push_back(string(s[0].size(), '#')); + s.insert(s.begin(), string(s[0].size(), '#')); + for(auto& si: s) + si = '#'+si+'#'; + + const int H = s.size(), W = s[0].size(); + const int NOTYET = 0x7fffffff; + + vector> tree; + vector> parent_cand(H, vector(W, -1)); + vector> color(H, vector(W, NOTYET)); + for(int y=0; y tonari; + + queue> Q; + color[y][x] = newId; + Q.emplace(y, x); + while(!Q.empty()) { + int yy = Q.front().first; + int xx = Q.front().second; + Q.pop(); + + int dx[] = {-1,+1,0,0}; + int dy[] = {0,0,-1,+1}; + for(int d=0; d<4; ++d) { + int y2 = yy+dy[d]; + int x2 = xx+dx[d]; + if(0<=x2&&x2, int> hashId; + bool tree_eq(const vector>& a, const vector>& b) + { + return hash(a,0) == hash(b,0); + } + + int hash(const vector>& a, int r) + { + vector ch; + for(int v: a[r]) + ch.push_back(hash(a, v)); + sort(ch.begin(), ch.end()); + if(hashId.count(ch)) + return hashId[ch]; + int v = hashId.size(); + return hashId[ch] = v; + } +}; + +// 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 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(_, Balance().canTransform(initial, target));} +int main(){ + +CASE(0) + string initial_[] = {"#"}; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = {"."}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "Impossible"; +END +CASE(1) + string initial_[] = {"..", + ".."}; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = {".#", + "##"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "Possible"; +END +CASE(2) + string initial_[] = {"...", + ".#.", + "..."}; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = {"###", + "#.#", + "###"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "Impossible"; +END +CASE(3) + string initial_[] = {".#.#.......", + "####.###...", + ".....####..", + "..##.#.##.#", + ".##..#.##.#", + ".#######...", + ".#....###.#", + ".##.#.#....", + "..#...#...#", + "..#####...#", + "..........."}; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = {"...........", + ".###....#..", + ".#.#..#....", + ".###.......", + ".#####.....", + ".#...#####.", + ".#.#.....#.", + ".#.#####.#.", + ".#.......#.", + ".#########.", + "..........."}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "Impossible"; +END +CASE(4) + string initial_[] = {".....", + ".###.", + ".....", + ".###.", + "....."}; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = {".....", + ".#.#.", + ".#.#.", + ".#.#.", + "....."}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "Possible"; +END +/* +CASE(5) + string initial_[] = ; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = ; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = ; +END +CASE(6) + string initial_[] = ; + vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); + string target_[] = ; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = ; +END +*/ + +} +// END CUT HERE DELETED SRM/TCO15-2B/1A.cpp Index: SRM/TCO15-2B/1A.cpp ================================================================== --- SRM/TCO15-2B/1A.cpp +++ SRM/TCO15-2B/1A.cpp @@ -1,86 +0,0 @@ -#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 Bitwisdom { public: - double expectedActions(vector p) - { - double e = 0; - for(int i=1; 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 double& Expected, const double& Received) { - bool ok = (abs(Expected - Received) < 1e-9); - 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(_, Bitwisdom().expectedActions(p));} -int main(){ - -CASE(0) - int p_[] = {100, 100, 100}; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = 1.0; -END -CASE(1) - int p_[] = {50, 50}; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = 0.75; -END -CASE(2) - int p_[] = {0, 40, 50, 60}; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = 1.4; -END -CASE(3) - int p_[] = {37, 63, 23, 94, 12}; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = 2.6820475464; -END -/* -CASE(4) - int p_[] = ; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = ; -END -CASE(5) - int p_[] = ; - vector p(p_, p_+sizeof(p_)/sizeof(*p_)); - double _ = ; -END -*/ -} -// END CUT HERE DELETED SRM/TCO15-2B/1B.cpp Index: SRM/TCO15-2B/1B.cpp ================================================================== --- SRM/TCO15-2B/1B.cpp +++ SRM/TCO15-2B/1B.cpp @@ -1,204 +0,0 @@ -#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 Balance { public: - string canTransform(vector initial, vector target) - { - auto ti = gen_tree(initial); - auto tt = gen_tree(target); - return tree_eq(ti, tt) ? "Possible" : "Impossible"; - } - - vector> gen_tree(vector s) { - s.push_back(string(s[0].size(), '#')); - s.insert(s.begin(), string(s[0].size(), '#')); - for(auto& si: s) - si = '#'+si+'#'; - - const int H = s.size(), W = s[0].size(); - const int NOTYET = 0x7fffffff; - - vector> tree; - vector> parent_cand(H, vector(W, -1)); - vector> color(H, vector(W, NOTYET)); - for(int y=0; y tonari; - - queue> Q; - color[y][x] = newId; - Q.emplace(y, x); - while(!Q.empty()) { - int yy = Q.front().first; - int xx = Q.front().second; - Q.pop(); - - int dx[] = {-1,+1,0,0}; - int dy[] = {0,0,-1,+1}; - for(int d=0; d<4; ++d) { - int y2 = yy+dy[d]; - int x2 = xx+dx[d]; - if(0<=x2&&x2, int> hashId; - bool tree_eq(const vector>& a, const vector>& b) - { - return hash(a,0) == hash(b,0); - } - - int hash(const vector>& a, int r) - { - vector ch; - for(int v: a[r]) - ch.push_back(hash(a, v)); - sort(ch.begin(), ch.end()); - if(hashId.count(ch)) - return hashId[ch]; - int v = hashId.size(); - return hashId[ch] = v; - } -}; - -// 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 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(_, Balance().canTransform(initial, target));} -int main(){ - -CASE(0) - string initial_[] = {"#"}; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = {"."}; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = "Impossible"; -END -CASE(1) - string initial_[] = {"..", - ".."}; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = {".#", - "##"}; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = "Possible"; -END -CASE(2) - string initial_[] = {"...", - ".#.", - "..."}; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = {"###", - "#.#", - "###"}; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = "Impossible"; -END -CASE(3) - string initial_[] = {".#.#.......", - "####.###...", - ".....####..", - "..##.#.##.#", - ".##..#.##.#", - ".#######...", - ".#....###.#", - ".##.#.#....", - "..#...#...#", - "..#####...#", - "..........."}; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = {"...........", - ".###....#..", - ".#.#..#....", - ".###.......", - ".#####.....", - ".#...#####.", - ".#.#.....#.", - ".#.#####.#.", - ".#.......#.", - ".#########.", - "..........."}; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = "Impossible"; -END -CASE(4) - string initial_[] = {".....", - ".###.", - ".....", - ".###.", - "....."}; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = {".....", - ".#.#.", - ".#.#.", - ".#.#.", - "....."}; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = "Possible"; -END -/* -CASE(5) - string initial_[] = ; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = ; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = ; -END -CASE(6) - string initial_[] = ; - vector initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_)); - string target_[] = ; - vector target(target_, target_+sizeof(target_)/sizeof(*target_)); - string _ = ; -END -*/ - -} -// END CUT HERE ADDED SRM/TCO15-2C-U/1A.cpp Index: SRM/TCO15-2C-U/1A.cpp ================================================================== --- SRM/TCO15-2C-U/1A.cpp +++ SRM/TCO15-2C-U/1A.cpp @@ -0,0 +1,119 @@ +#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 YetAnotherCardGame { public: + int maxCards(vector petr, vector snuke) + { + sort(petr.begin(), petr.end()); + sort(snuke.begin(), snuke.end()); + + return rec(&petr, &snuke, 0, 0, 0, 0, 0); + } + + map,int> memo; + int rec(const vector* me, const vector* you, + int turn, int m_next, int y_next, int m_musteat, int y_musteat) + { + if(m_musteat>=0 && m_next+m_musteat==me->size()) + return 0; + + tuple key(turn,m_next,y_next,m_musteat,y_musteat); + if(memo.count(key)) + return memo[key]; + + // eat + int best = rec(you,me,turn^1,y_next,m_next,y_musteat,m_musteat+1); + + // play + if(m_next < me->size()) { + int v = (*me)[m_next]; + m_next++; + while(m_nextsize() && (*me)[m_next]<=v) + m_next++, m_musteat--; + while(y_nextsize() && (*you)[y_next]<=v) + y_next++, y_musteat--; + best = max(best, 1+rec(you,me,turn^1,y_next,m_next,y_musteat,m_musteat)); + } + + return memo[key] = 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(_, YetAnotherCardGame().maxCards(petr, snuke));} +int main(){ + +CASE(0) + int petr_[] = {2, 5}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {3, 1}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = 3; +END +CASE(1) + int petr_[] = {1, 1, 1, 1, 1}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {1, 1, 1, 1, 1}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = 1; +END +CASE(2) + int petr_[] = {1, 4, 6, 7, 3}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {1, 7, 1, 5, 7}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = 6; +END +CASE(3) + int petr_[] = {19, 99, 86, 30, 98, 68, 73, 92, 37, 69, 93, 28, 58, 36, 86, 32, 46, 34, 71, 29}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {28, 29, 22, 75, 78, 75, 39, 41, 5, 14, 100, 28, 51, 42, 9, 25, 12, 59, 98, 83}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = 28; +END +CASE(4) + int petr_[] = {69,32,81,40,44,69,80,13,46,34,100,93,81,46,72,10,98,27,27,82,25,52,3,87,77,4,70,87,82,24,4,5,41,97,41,28,12,49,78,37,37,20,70,68,20,76,53,59,25,77}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {52,76,64,82,37,76,31,5,54,53,98,12,26,22,80,8,5,21,48,44,11,82,9,37,21,60,43,63,29,73,66,46,20,70,83,60,41,61,41,48,11,32,14,39,89,18,74,8,11,84}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = -1; +END +CASE(5) + int petr_[] = {7,2,7,5,8,1,3,5,7,4,4,8,6,5,8,8,8,4,1,2,1,2,6,3,1,5,2,3,8,2,6,4,3,2,5,4,7,3,6,3,2,6,4,4,3,4,1,1,3,4}; + vector petr(petr_, petr_+sizeof(petr_)/sizeof(*petr_)); + int snuke_[] = {7,3,6,7,8,4,7,3,2,1,3,6,8,7,8,2,8,8,7,7,8,5,7,6,2,1,8,5,4,4,8,8,1,4,7,7,7,4,1,8,6,6,1,3,8,4,1,4,2,5}; + vector snuke(snuke_, snuke_+sizeof(snuke_)/sizeof(*snuke_)); + int _ = -1; +END +} +// END CUT HERE