ADDED SRM/539-U/1A.cpp Index: SRM/539-U/1A.cpp ================================================================== --- SRM/539-U/1A.cpp +++ SRM/539-U/1A.cpp @@ -0,0 +1,143 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +#include <cstring> +#ifdef __GNUC__ +#include <ext/hash_map> +#define unordered_map __gnu_cxx::hash_map +#else +#include <unordered_map> +#endif +using namespace std; +typedef long long LL; +typedef complex<double> CMP; + +class Over9000Rocks { public: + int countPossibilities(vector <int> lowerBound, vector <int> upperBound) + { + vector< pair<int,bool> > ev; + const int MIN = 9001; + const int N = lowerBound.size(); + for(int mask=1; mask<(1<<N); ++mask) + { + int lo=0, hi=0; + for(int i=0; i<N; ++i) + if( mask & (1<<i) ) { + lo += lowerBound[i]; + hi += upperBound[i]; + } + if(hi<MIN) + continue; + lo = max(lo, MIN); + ev.push_back( make_pair(lo,true) ); + ev.push_back( make_pair(hi+1,false) ); + } + sort(ev.begin(), ev.end()); + int nest = 0; + int entered = -1; + int total = 0; + for(int k=0; k<ev.size(); ++k) + { + int x = ev[k].first; + bool in = ev[k].second; + if( nest == 0 ) { + if( in ) + entered = x; + } else if( nest == 1 ) { + if( !in ) + total += (x - entered); + } + if(in) nest++; else nest--; + } + return total; + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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(_, Over9000Rocks().countPossibilities(lowerBound, upperBound));} +int main(){ + +CASE(0) + int lowerBound_[] = {9000}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9001}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 1; +END +CASE(1) + int lowerBound_[] = {9000, 1, 10}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9000, 2, 20}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 15; +END +CASE(2) + int lowerBound_[] = {1001, 2001, 3001, 3001}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {1003, 2003, 3003, 3003}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 9; +END +CASE(3) + int lowerBound_[] = {9000,90000,1,10}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9000,90000,3,15}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 38; +END +CASE(4) + int lowerBound_[] = {1,1,1,1,1,1}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {3,4,5,6,7,8}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 0; +END +CASE(5) + int lowerBound_[] = {242,7393,3738,2594,3051,7711,3386,4363,6035,4752,5384,7607,5702,2226,7792}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9138,9120,9027,9185,9081,9114,9044,9089,9178,9103,9089,9026,9129,9050,9173}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = -1; +END +CASE(6) + int lowerBound_[] = {9001}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9002}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 2; +END +CASE(7) + int lowerBound_[] = {9000, 1, 2, 3}; + vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_)); + int upperBound_[] = {9000, 1, 2, 3}; + vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_)); + int _ = 10; +END + +} +// END CUT HERE ADDED SRM/539-U/1B-U.cpp Index: SRM/539-U/1B-U.cpp ================================================================== --- SRM/539-U/1B-U.cpp +++ SRM/539-U/1B-U.cpp @@ -0,0 +1,159 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +#include <cstring> +#ifdef __GNUC__ +#include <ext/hash_map> +#define unordered_map __gnu_cxx::hash_map +#else +#include <unordered_map> +#endif +using namespace std; +typedef long long LL; +typedef complex<double> CMP; + +static const int INF = 0x3fffffff; + +typedef int vert; +typedef vert edge; +typedef vector<edge> edges; +typedef vector<edges> graph; + +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) +{ + for(int i=0; i<G[v].size(); ++i) { + vert u = G[v][i]; + if( visited[u] ) continue; + visited[u] = true; + + if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) + { matchTo[v]=u, matchTo[u]=v; return true; } + } + return false; +} + +template<int NV> +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right + // only left->right edges are used during computation +{ + vector<vert> matchTo(G.size(), -1); + int ans = 0; + for(vert v=0; v<L; ++v) { + bool visited[NV] = {}; + if( augment(G, v, matchTo, visited) ) + ++ans; + } + return ans; +} + +class SafeReturn { public: + int minRisk(int N, vector <string> streets) + { + int T = streets.size(); + vector< vector<int> > g(T, vector<int>(T, INF)); + for(int i=0; i<T; ++i) + for(int j=0; j<T; ++j) + if( i == j ) + g[i][j] = 0; + else if( streets[i][j] != '-' ) + g[i][j] = streets[i][j] - '0'; + vector< vector<int> > d = g; + for(int k=0; k<T; ++k) + for(int i=0; i<T; ++i) + for(int j=0; j<T; ++j) + d[i][j] = min(d[i][j], d[i][k]+d[k][j]); + + graph G(2*(N+1)); + for(int x=0; x<=N; ++x) + for(int y=0; y<=N; ++y) if( x != y ) + { + if( d[0][x] + d[x][y] == d[0][y] ) + { + G[x].push_back(N+1+y); + } + } + return N+1 - biMatch<256>(G, N+1); + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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(_, SafeReturn().minRisk(N, streets));} +int main(){ + +CASE(0) + int N = 3; + string streets_[] = {"-234", + "2---", + "3---", + "4---"}; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = 3; +END +CASE(1) + int N = 2; + string streets_[] = {"-12", + "1-1", + "21-"}; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = 1; +END +CASE(2) + int N = 3; + string streets_[] = {"-----7", + "--1---", + "-1-5--", + "--5-1-", + "---1-3", + "7---3-"}; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = 1; +END +CASE(3) + int N = 2; + string streets_[] = {"-11", + "1-1", + "11-"}; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = 2; +END +/* +CASE(4) + int N = ; + string streets_[] = ; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = ; +END +CASE(5) + int N = ; + string streets_[] = ; + vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/539-U/1C-U.cpp Index: SRM/539-U/1C-U.cpp ================================================================== --- SRM/539-U/1C-U.cpp +++ SRM/539-U/1C-U.cpp @@ -0,0 +1,229 @@ +#include <iostream> +#include <sstream> +#include <iomanip> +#include <vector> +#include <string> +#include <map> +#include <set> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <functional> +#include <complex> +#include <queue> +#include <stack> +#include <cmath> +#include <cassert> +#include <cstring> +#ifdef __GNUC__ +#include <ext/hash_map> +#define unordered_map __gnu_cxx::hash_map +#else +#include <unordered_map> +#endif +using namespace std; +typedef long long LL; +typedef complex<double> CMP; + +template<typename T> +class IdGen +{ + map<T, int> v2id_; + vector<T> id2v_; +public: + int v2id(const T& v) { + if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } + return v2id_[v]; + } + const T& id2v(int i) const { return id2v_[i]; } + int size() const { return id2v_.size(); } +}; + +typedef int vert; +typedef vert edge; +typedef vector<edge> edges; +typedef vector<edges> graph; + +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) +{ + for(int i=0; i<G[v].size(); ++i) { + vert u = G[v][i]; + if( visited[u] ) continue; + visited[u] = true; + + if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) + { matchTo[v]=u, matchTo[u]=v; return true; } + } + return false; +} + +template<int NV> +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right + // only left->right edges are used during computation +{ + vector<vert> matchTo(G.size(), -1); + int ans = 0; + for(vert v=0; v<L; ++v) { + bool visited[NV] = {}; + if( augment(G, v, matchTo, visited) ) + ++ans; + } + return ans; +} + +class FoxBomb { public: + int getMinimumCost(vector <string> grid) + { + int H = grid.size(); + int W = grid[0].size(); + + IdGen< pair< int,pair<int,int> > > hline; + for(int y=0; y<H; ++y) + for(int sx=0; sx<W; ) + { + if( grid[y][sx] == '#' ) + {++sx; continue;} + int ex = sx+1; + for(; ex<W && grid[y][ex]=='.'; ++ex) {} + if( sx+1 < ex ) + hline.v2id( make_pair(y, make_pair(sx,ex)) ); + sx = ex; + } + + IdGen< pair< int,pair<int,int> > > vline; + for(int x=0; x<W; ++x) + for(int sy=0; sy<H; ) + { + if( grid[sy][x] == '#' ) + {++sy; continue;} + int ey = sy+1; + for(; ey<H && grid[ey][x]=='.'; ++ey) {} + if( sy+1 < ey ) + vline.v2id( make_pair(x, make_pair(sy,ey)) ); + sy = ey; + } + + graph G(hline.size() + vline.size()); + for(int i=0; i<hline.size(); ++i) + for(int k=0; k<vline.size(); ++k) + { + const pair< int,pair<int,int> >& hh = hline.id2v(i); + const pair< int,pair<int,int> >& vv = vline.id2v(k); + int y = hh.first; + int sx = hh.second.first; + int ex = hh.second.second; + int x = vv.first; + int sy = vv.second.first; + int ey = vv.second.second; + if( sx<=x && x<ex && sy<=y && y<ey ) + G[i].push_back(hline.size()+k); + } + + int dots = 0; + for(int y=0; y<H; ++y) + for(int x=0; x<W; ++x) if( grid[y][x]=='.' ) + { + int dy[]={-1,+1,0,0}; + int dx[]={0,0,-1,+1}; + bool non_wall = false; + for(int i=0; i<4; ++i) { + int yy = y+dy[i]; + int xx = x+dx[i]; + if(0<=yy&&yy<H&&0<=xx&&xx<W&&grid[yy][xx]=='.') + non_wall = true; + } + if(!non_wall) + dots++; + } + + return dots + G.size() - biMatch<2500>(G, hline.size()); + } +}; + +// BEGIN CUT HERE +#include <ctime> +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) + { os << "{ "; + for(typename vector<T>::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(_, FoxBomb().getMinimumCost(grid));} +int main(){ + +CASE(0) + string grid_[] = {"#..." +,"..##" +,"#.##"}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 2; +END +CASE(1) + string grid_[] = {".#.#.#." +,"......." +,".#.#.#."}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 4; +END +CASE(2) + string grid_[] = {"######################################" +,"######################################" +,"###.....................##############" +,"###.###################.###....#...###" +,"###.###################.###.######.###" +,"###.###################.###.######.###" +,"###.###################.###.######.###" +,"###.###################.###.######.###" +,"###.###################.###.######.###" +,"###.........####........###.######.###" +,"###########.###########.###........###" +,"###########.###########.##########.###" +,"###########.###########.##########.###" +,"###########.###########.##########.###" +,"###########.###########.##########.###" +,"##..........##..........##########.###" +,"#######################............###" +,"######################################"}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 9; +END +CASE(3) + string grid_[] = {".#." +,"..." +,"#.#" +,"..." +,".#."} +; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 5; +END +CASE(4) + string grid_[] = {"."}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 1; +END +CASE(5) +string grid_[] = {"..."}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 1; +END +CASE(6) +string grid_[] = {".",".","."}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 1; +END +CASE(7) +string grid_[] = { + "...#.", + "####.", + "...#."}; + vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); + int _ = 3; +END +} +// END CUT HERE