• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/539-U/1A.cpp version [ab9100cd4e760130]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class Over9000Rocks { public:
           29  + int countPossibilities(vector <int> lowerBound, vector <int> upperBound)
           30  + {
           31  +  vector< pair<int,bool> > ev;
           32  +  const int MIN = 9001;
           33  +  const int N = lowerBound.size();
           34  +  for(int mask=1; mask<(1<<N); ++mask)
           35  +  {
           36  +   int lo=0, hi=0;
           37  +   for(int i=0; i<N; ++i)
           38  +    if( mask & (1<<i) ) {
           39  +     lo += lowerBound[i];
           40  +     hi += upperBound[i];
           41  +    }
           42  +   if(hi<MIN)
           43  +    continue;
           44  +   lo = max(lo, MIN);
           45  +   ev.push_back( make_pair(lo,true) );
           46  +   ev.push_back( make_pair(hi+1,false) );
           47  +  }
           48  +  sort(ev.begin(), ev.end());
           49  +  int nest = 0;
           50  +  int entered = -1;
           51  +  int total = 0;
           52  +  for(int k=0; k<ev.size(); ++k)
           53  +  {
           54  +   int x = ev[k].first;
           55  +   bool in = ev[k].second;
           56  +   if( nest == 0 ) {
           57  +    if( in )
           58  +     entered = x;
           59  +   } else if( nest == 1 ) {
           60  +    if( !in )
           61  +     total += (x - entered);
           62  +   }
           63  +   if(in) nest++; else nest--;
           64  +  }
           65  +  return total;
           66  + }
           67  +};
           68  +
           69  +// BEGIN CUT HERE
           70  +#include <ctime>
           71  +double start_time; string timer()
           72  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           73  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           74  + { os << "{ ";
           75  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           76  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           77  +void verify_case(const int& Expected, const int& Received) {
           78  + bool ok = (Expected == Received);
           79  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           80  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           81  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           82  +#define END  verify_case(_, Over9000Rocks().countPossibilities(lowerBound, upperBound));}
           83  +int main(){
           84  +
           85  +CASE(0)
           86  + int lowerBound_[] = {9000};
           87  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
           88  + int upperBound_[] = {9001};
           89  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
           90  + int _ = 1;
           91  +END
           92  +CASE(1)
           93  + int lowerBound_[] = {9000, 1, 10};
           94  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
           95  + int upperBound_[] = {9000, 2, 20};
           96  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
           97  + int _ = 15;
           98  +END
           99  +CASE(2)
          100  + int lowerBound_[] = {1001, 2001, 3001, 3001};
          101  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          102  + int upperBound_[] = {1003, 2003, 3003, 3003};
          103  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          104  + int _ = 9;
          105  +END
          106  +CASE(3)
          107  + int lowerBound_[] = {9000,90000,1,10};
          108  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          109  + int upperBound_[] = {9000,90000,3,15};
          110  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          111  + int _ = 38;
          112  +END
          113  +CASE(4)
          114  + int lowerBound_[] = {1,1,1,1,1,1};
          115  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          116  + int upperBound_[] = {3,4,5,6,7,8};
          117  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          118  + int _ = 0;
          119  +END
          120  +CASE(5)
          121  + int lowerBound_[] = {242,7393,3738,2594,3051,7711,3386,4363,6035,4752,5384,7607,5702,2226,7792};
          122  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          123  + int upperBound_[] = {9138,9120,9027,9185,9081,9114,9044,9089,9178,9103,9089,9026,9129,9050,9173};
          124  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          125  + int _ = -1;
          126  +END
          127  +CASE(6)
          128  + int lowerBound_[] = {9001};
          129  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          130  +   int upperBound_[] = {9002};
          131  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          132  + int _ = 2;
          133  +END
          134  +CASE(7)
          135  + int lowerBound_[] = {9000, 1, 2, 3};
          136  +   vector <int> lowerBound(lowerBound_, lowerBound_+sizeof(lowerBound_)/sizeof(*lowerBound_));
          137  +   int upperBound_[] = {9000, 1, 2, 3};
          138  +   vector <int> upperBound(upperBound_, upperBound_+sizeof(upperBound_)/sizeof(*upperBound_));
          139  + int _ = 10;
          140  +END
          141  +
          142  +}
          143  +// END CUT HERE

Added SRM/539-U/1B-U.cpp version [fb6029affb2ad4b9]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +static const int INF = 0x3fffffff;
           29  +
           30  +typedef int           vert;
           31  +typedef vert          edge;
           32  +typedef vector<edge>  edges;
           33  +typedef vector<edges> graph;
           34  +
           35  +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
           36  +{
           37  + for(int i=0; i<G[v].size(); ++i) {
           38  +  vert u = G[v][i];
           39  +  if( visited[u] ) continue;
           40  +  visited[u] = true;
           41  +
           42  +  if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
           43  +   { matchTo[v]=u, matchTo[u]=v; return true; }
           44  + }
           45  + return false;
           46  +}
           47  +
           48  +template<int NV>
           49  +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
           50  +    // only left->right edges are used during computation
           51  +{
           52  + vector<vert> matchTo(G.size(), -1);
           53  + int ans = 0;
           54  + for(vert v=0; v<L; ++v) {
           55  +  bool visited[NV] = {};
           56  +  if( augment(G, v, matchTo, visited) )
           57  +   ++ans;
           58  + }
           59  + return ans;
           60  +}
           61  +
           62  +class SafeReturn { public:
           63  + int minRisk(int N, vector <string> streets)
           64  + {
           65  +  int T = streets.size();
           66  +  vector< vector<int> > g(T, vector<int>(T, INF));
           67  +  for(int i=0; i<T; ++i)
           68  +   for(int j=0; j<T; ++j)
           69  +    if( i == j )
           70  +     g[i][j] = 0;
           71  +    else if( streets[i][j] != '-' )
           72  +     g[i][j] = streets[i][j] - '0';
           73  +  vector< vector<int> > d = g;
           74  +  for(int k=0; k<T; ++k)
           75  +   for(int i=0; i<T; ++i)
           76  +    for(int j=0; j<T; ++j)
           77  +     d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
           78  +
           79  +  graph G(2*(N+1));
           80  +  for(int x=0; x<=N; ++x)
           81  +  for(int y=0; y<=N; ++y) if( x != y )
           82  +  {
           83  +   if( d[0][x] + d[x][y] == d[0][y] )
           84  +   {
           85  +    G[x].push_back(N+1+y);
           86  +   }
           87  +  }
           88  +  return N+1 - biMatch<256>(G, N+1);
           89  + }
           90  +};
           91  +
           92  +// BEGIN CUT HERE
           93  +#include <ctime>
           94  +double start_time; string timer()
           95  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           96  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           97  + { os << "{ ";
           98  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           99  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          100  +void verify_case(const int& Expected, const int& Received) {
          101  + bool ok = (Expected == Received);
          102  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          103  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          104  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          105  +#define END  verify_case(_, SafeReturn().minRisk(N, streets));}
          106  +int main(){
          107  +
          108  +CASE(0)
          109  + int N = 3;
          110  + string streets_[] = {"-234",
          111  + "2---",
          112  + "3---",
          113  + "4---"};
          114  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          115  + int _ = 3;
          116  +END
          117  +CASE(1)
          118  + int N = 2;
          119  + string streets_[] = {"-12",
          120  + "1-1",
          121  + "21-"};
          122  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          123  + int _ = 1;
          124  +END
          125  +CASE(2)
          126  + int N = 3;
          127  + string streets_[] = {"-----7",
          128  + "--1---",
          129  + "-1-5--",
          130  + "--5-1-",
          131  + "---1-3",
          132  + "7---3-"};
          133  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          134  + int _ = 1;
          135  +END
          136  +CASE(3)
          137  + int N = 2;
          138  + string streets_[] = {"-11",
          139  + "1-1",
          140  + "11-"};
          141  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          142  + int _ = 2;
          143  +END
          144  +/*
          145  +CASE(4)
          146  + int N = ;
          147  + string streets_[] = ;
          148  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          149  + int _ = ;
          150  +END
          151  +CASE(5)
          152  + int N = ;
          153  + string streets_[] = ;
          154  +   vector <string> streets(streets_, streets_+sizeof(streets_)/sizeof(*streets_));
          155  + int _ = ;
          156  +END
          157  +*/
          158  +}
          159  +// END CUT HERE

Added SRM/539-U/1C-U.cpp version [73a81491ebb9328c]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +template<typename T>
           29  +class IdGen
           30  +{
           31  + map<T, int> v2id_;
           32  + vector<T>   id2v_;
           33  +public:
           34  + int v2id(const T& v) {
           35  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           36  +  return v2id_[v];
           37  + }
           38  + const T& id2v(int i) const { return id2v_[i]; }
           39  + int size() const { return id2v_.size(); }
           40  +};
           41  +
           42  +typedef int           vert;
           43  +typedef vert          edge;
           44  +typedef vector<edge>  edges;
           45  +typedef vector<edges> graph;
           46  +
           47  +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
           48  +{
           49  + for(int i=0; i<G[v].size(); ++i) {
           50  +  vert u = G[v][i];
           51  +  if( visited[u] ) continue;
           52  +  visited[u] = true;
           53  +
           54  +  if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
           55  +   { matchTo[v]=u, matchTo[u]=v; return true; }
           56  + }
           57  + return false;
           58  +}
           59  +
           60  +template<int NV>
           61  +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
           62  +    // only left->right edges are used during computation
           63  +{
           64  + vector<vert> matchTo(G.size(), -1);
           65  + int ans = 0;
           66  + for(vert v=0; v<L; ++v) {
           67  +  bool visited[NV] = {};
           68  +  if( augment(G, v, matchTo, visited) )
           69  +   ++ans;
           70  + }
           71  + return ans;
           72  +}
           73  +
           74  +class FoxBomb { public:
           75  + int getMinimumCost(vector <string> grid)
           76  + {
           77  +  int H = grid.size();
           78  +  int W = grid[0].size();
           79  +
           80  +  IdGen< pair< int,pair<int,int> > > hline;
           81  +  for(int y=0; y<H; ++y)
           82  +   for(int sx=0; sx<W; )
           83  +   {
           84  +    if( grid[y][sx] == '#' )
           85  +     {++sx; continue;}
           86  +    int ex = sx+1;
           87  +    for(; ex<W && grid[y][ex]=='.'; ++ex) {}
           88  +    if( sx+1 < ex )
           89  +     hline.v2id( make_pair(y, make_pair(sx,ex)) );
           90  +    sx = ex;
           91  +   }
           92  +
           93  +  IdGen< pair< int,pair<int,int> > > vline;
           94  +  for(int x=0; x<W; ++x)
           95  +   for(int sy=0; sy<H; )
           96  +   {
           97  +    if( grid[sy][x] == '#' )
           98  +     {++sy; continue;}
           99  +    int ey = sy+1;
          100  +    for(; ey<H && grid[ey][x]=='.'; ++ey) {}
          101  +    if( sy+1 < ey )
          102  +     vline.v2id( make_pair(x, make_pair(sy,ey)) );
          103  +    sy = ey;
          104  +   }
          105  +
          106  +  graph G(hline.size() + vline.size());
          107  +  for(int i=0; i<hline.size(); ++i)
          108  +   for(int k=0; k<vline.size(); ++k)
          109  +   {
          110  +    const pair< int,pair<int,int> >& hh = hline.id2v(i);
          111  +    const pair< int,pair<int,int> >& vv = vline.id2v(k);
          112  +    int y = hh.first;
          113  +    int sx = hh.second.first;
          114  +    int ex = hh.second.second;
          115  +    int x = vv.first;
          116  +    int sy = vv.second.first;
          117  +    int ey = vv.second.second;
          118  +    if( sx<=x && x<ex && sy<=y && y<ey )
          119  +     G[i].push_back(hline.size()+k);
          120  +   }
          121  +
          122  +  int dots = 0;
          123  +  for(int y=0; y<H; ++y)
          124  +   for(int x=0; x<W; ++x) if( grid[y][x]=='.' )
          125  +   {
          126  +    int dy[]={-1,+1,0,0};
          127  +    int dx[]={0,0,-1,+1};
          128  +    bool non_wall = false;
          129  +    for(int i=0; i<4; ++i) {
          130  +     int yy = y+dy[i];
          131  +     int xx = x+dx[i];
          132  +     if(0<=yy&&yy<H&&0<=xx&&xx<W&&grid[yy][xx]=='.')
          133  +      non_wall = true;
          134  +    }
          135  +    if(!non_wall)
          136  +     dots++;
          137  +   }
          138  +
          139  +  return dots + G.size() - biMatch<2500>(G, hline.size());
          140  + }
          141  +};
          142  +
          143  +// BEGIN CUT HERE
          144  +#include <ctime>
          145  +double start_time; string timer()
          146  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          147  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          148  + { os << "{ ";
          149  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          150  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          151  +void verify_case(const int& Expected, const int& Received) {
          152  + bool ok = (Expected == Received);
          153  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          154  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          155  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          156  +#define END  verify_case(_, FoxBomb().getMinimumCost(grid));}
          157  +int main(){
          158  +
          159  +CASE(0)
          160  + string grid_[] = {"#..."
          161  +,"..##"
          162  +,"#.##"};
          163  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          164  + int _ = 2;
          165  +END
          166  +CASE(1)
          167  + string grid_[] = {".#.#.#."
          168  +,"......."
          169  +,".#.#.#."};
          170  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          171  + int _ = 4;
          172  +END
          173  +CASE(2)
          174  + string grid_[] = {"######################################"
          175  +,"######################################"
          176  +,"###.....................##############"
          177  +,"###.###################.###....#...###"
          178  +,"###.###################.###.######.###"
          179  +,"###.###################.###.######.###"
          180  +,"###.###################.###.######.###"
          181  +,"###.###################.###.######.###"
          182  +,"###.###################.###.######.###"
          183  +,"###.........####........###.######.###"
          184  +,"###########.###########.###........###"
          185  +,"###########.###########.##########.###"
          186  +,"###########.###########.##########.###"
          187  +,"###########.###########.##########.###"
          188  +,"###########.###########.##########.###"
          189  +,"##..........##..........##########.###"
          190  +,"#######################............###"
          191  +,"######################################"};
          192  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          193  + int _ = 9;
          194  +END
          195  +CASE(3)
          196  + string grid_[] = {".#."
          197  +,"..."
          198  +,"#.#"
          199  +,"..."
          200  +,".#."}
          201  +;
          202  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          203  + int _ = 5;
          204  +END
          205  +CASE(4)
          206  + string grid_[] = {"."};
          207  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          208  + int _ = 1;
          209  +END
          210  +CASE(5)
          211  +string grid_[] = {"..."};
          212  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          213  + int _ = 1;
          214  +END
          215  +CASE(6)
          216  +string grid_[] = {".",".","."};
          217  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          218  + int _ = 1;
          219  +END
          220  +CASE(7)
          221  +string grid_[] = {
          222  + "...#.",
          223  + "####.",
          224  + "...#."};
          225  +   vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
          226  + int _ = 3;
          227  +END
          228  +}
          229  +// END CUT HERE