ADDED SRM/655-U/1A.cpp Index: SRM/655-U/1A.cpp ================================================================== --- SRM/655-U/1A.cpp +++ SRM/655-U/1A.cpp @@ -0,0 +1,164 @@ +#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 BichromePainting { public: + string isThatPossible(vector board, int k) + { + return solve(board, k) ? "Possible" : "Impossible"; + } + + bool solve(vector board, int K) + { + while(!no_black(board)) + if(!step_back(board, K)) + return false; + return true; + } + + bool no_black(const vector& board) + { + const int H = board.size(); + const int W = board[0].size(); + for(int y=0; y& board, int K) { + bool updated = false; + + const int H = board.size(); + const int W = board[0].size(); + for(int y=0; y+K<=H; ++y) + for(int x=0; x+K<=W; ++x) { + bool has_white = false; + bool has_black = false; + for(int dy=0; dy +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(_, BichromePainting().isThatPossible(board, k));} +int main(){ + +CASE(0) + string board_[] = {"BBBW", + "BWWW", + "BWWW", + "WWWW"}; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 3; + string _ = "Possible"; +END +CASE(1) + string board_[] = {"BW", + "WB"} +; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 2; + string _ = "Impossible"; +END +CASE(2) + string board_[] = {"BWBWBB", + "WBWBBB", + "BWBWBB", + "WBWBBB", + "BBBBBB", + "BBBBBB"} +; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 2; + string _ = "Possible"; +END +CASE(3) + string board_[] = {"BWBWBB", + "WBWBWB", + "BWBWBB", + "WBWBWB", + "BWBWBB", + "BBBBBB"} +; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 2; + string _ = "Impossible"; +END +CASE(4) + string board_[] = {"BWBWBB", + "WBWBWB", + "BWBWBB", + "WBWBWB", + "BWBWBB", + "BBBBBB"} +; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 1; + string _ = "Possible"; +END +CASE(5) + string board_[] = {"BB", + "BB"}; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 2; + string _ = "Possible"; +END +CASE(6) +string board_[] = {"BBWW", "BBWW", "WBBW", "WWWW"}; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = 2; + string _ = "Possible"; +END +/* +CASE(7) + string board_[] = ; + vector board(board_, board_+sizeof(board_)/sizeof(*board_)); + int k = ; + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/655-U/1B-U.cpp Index: SRM/655-U/1B-U.cpp ================================================================== --- SRM/655-U/1B-U.cpp +++ SRM/655-U/1B-U.cpp @@ -0,0 +1,151 @@ +#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 unsigned MODVAL = 1000000007; +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; } + +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } + +class Nine { public: + int count(int N, vector d) + { + const int M = d.size(); + + vector cnt(1<> pat(M+1, vector(9)); + pat[0][0] = 1; + for(int cnt=1; cnt<=M; ++cnt) { + for(int pre=0; pre<9; ++pre) + for(int incr=0; incr<=9; ++incr) + pat[cnt][(pre+incr)%9] += pat[cnt-1][pre]; + } + + int TBLMAX = 1; for(int i=0; i dp(TBLMAX); + dp[0] = 1; + + for(int mask=0; mask<(1< dp2(TBLMAX); + + for(int rem_state=0; rem_state +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(_, Nine().count(N, d));} +int main(){ + +CASE(0) + int N = 2; + int d_[] = {1,2}; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = 4; +END +CASE(1) + int N = 2; + int d_[] = {1,2,3}; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = 16; +END +CASE(2) + int N = 1; + int d_[] = {0,0,1}; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = 200; +END +CASE(3) + int N = 5; + int d_[] = {1,3,5,8,24,22,25,21,30,2,4,0,6,7,9,11,14,13,12,15,18,17,16,19,26,29,31,28,27,10,20,23}; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = 450877328; +END +CASE(4) + int N = 5; + int d_[] = {31,31,31,31,31}; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = 11112; +END +/* +CASE(5) + int N = ; + int d_[] = ; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = ; +END +CASE(6) + int N = ; + int d_[] = ; + vector d(d_, d_+sizeof(d_)/sizeof(*d_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/655-U/1C-U.cpp Index: SRM/655-U/1C-U.cpp ================================================================== --- SRM/655-U/1C-U.cpp +++ SRM/655-U/1C-U.cpp @@ -0,0 +1,289 @@ +#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; + +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } +double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } + +int ccw(const CMP& a, CMP b, CMP c) { + b -= a; c -= a; + if( outer_prod(b,c) > 0 ) return +1; // counter clockwise + if( outer_prod(b,c) < 0 ) return -1; // clockwise + if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line + if( norm(b) < norm(c) ) return -2; // a--b--c on line + return 0; +} + +bool byX( const CMP& a, const CMP& b ) { + if( a.real() != b.real() ) + return a.real() < b.real(); + return a.imag() < b.imag(); +} + +vector convex_hull( vector p ) +{ + #define IS_RIGHT <0 // skip on-line verts + //#define IS_RIGHT ==-1 // take all + + sort(p.begin(), p.end(), &byX); + + vector ans; + for(int i=0; i=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT ) + ans.pop_back(); + if( ans.size() == p.size() ) + return ans; + for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left + while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT ) + ans.pop_back(); + ans.pop_back(); + return ans; +} + +bool point_in_polygon( vector& ps, CMP p ) +{ + bool in = false; + for(int i=0; i b.imag()) swap(a,b); + if(a.imag()<=0 && 0 redX, vector redY, vector prob, vector blueX, vector blueY) + { + vector blue; + for(int i=0; i red; + vector p_red; + for(int i=0; i red_hull = convex_hull(red); + for(auto p: blue) + if(!point_in_polygon(red_hull, p)) + return 0.0; + + vector> rp; + for(int i=0; i& lhs, const pair& rhs) { + if(lhs == rhs) return false; + if(lhs.first == base) return true; + if(rhs.first == base) return false; + return arg(lhs.first - base) < arg(rhs.first - base); + }); + + function is_right_of_blue = [&](int ai, int bi) { + CMP a = rp[ai%N].first; + CMP b = rp[bi%N].first; + for(CMP p: blue) + if(ccw(a, b, p) != +1) + return false; + return true; // TODO + }; + + function rec; + map, double> memo; + rec = [&](int done_from, int done_to) { + if(done_from == done_to) + return 1.0; + + pair key(done_from, done_to); + if(memo.count(key)) + return memo[key]; + + double total = 0.0; + double pp = 1.0; + for(int next=done_to+1; next<=done_from; ++next) { + if(is_right_of_blue(done_to, next)) { + total += pp * (next==done_from ? 1.0 : rp[next].second) * rec(next, done_from); + } + pp *= 1.0 - rp[next].second; + } + return memo[key] = total; + }; + + double ans = 0.0; + for(int from=N; from>=2; --from) + for(int to=1; to +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(_, BichromeSky().totallyCovered(redX, redY, prob, blueX, blueY));} +int main(){ + +CASE(0) + int redX_[] = {3,-3,0}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {-1,-1,2}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {400,500,600}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {1,0,-1}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {0,1,0}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.12; +END +CASE(1) + int redX_[] = {3,-3,3,-3}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {3,3,-3,-3}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {200,300,400,500}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {0,1,-1}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {-1,-2,-2}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.088; +END +CASE(2) + int redX_[] = {3,-3,0}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {-1,-1,2}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {400,500,600}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {1,0,-1,123456}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {0,1,0,-654321}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.0; +END +CASE(3) + int redX_[] = {0,-2,-3,-4,-3,-2,0,2,3,4,3,2}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {4,3,2,0,-2,-3,-4,-3,-2,0,2,3}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {501,502,503,504,505,506,507,508,509,510,511,512}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {1,-1,-1,1}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {1,1,-1,-1}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.6555037822772468; +END +CASE(4) + int redX_[] = {0,1,-3,3}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {0,4,-2,-2}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {200,300,400,500}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {0,-1,1}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {1,-1,-1}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.06; +END +CASE(5) + int redX_[] = {10,-17,12,-11,-13,-10,-15,14,-4,2}; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = {8,17,-13,-19,-14,11,17,8,-8,-15}; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = {412,360,656,876,984,160,368,873,223,128}; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = {-9,-3,6,-9,-5,4,-3,10,-7,2}; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = {-6,10,10,-9,-10,-6,2,-10,-9,6}; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = 0.34037052019900405; +END +/* +CASE(6) + int redX_[] = ; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = ; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = ; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = ; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = ; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = ; +END +CASE(7) + int redX_[] = ; + vector redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_)); + int redY_[] = ; + vector redY(redY_, redY_+sizeof(redY_)/sizeof(*redY_)); + int prob_[] = ; + vector prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); + int blueX_[] = ; + vector blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_)); + int blueY_[] = ; + vector blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_)); + double _ = ; +END +*/ +} +// END CUT HERE