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

Added SRM/556-U/1A.cpp version [58cb8e25f4180cbe]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class LeftRightDigitsGame2 { public:
           23  + string minNumber(string digits, string lowerBound)
           24  + {
           25  +  return rec(digits, lowerBound);
           26  + }
           27  +
           28  + map<string, string> memo;
           29  + string rec(const string& digits, const string& lwb)
           30  + {
           31  +  if(lwb.size() == 0)
           32  +   return lwb;
           33  +  if(memo.count(lwb))
           34  +   return memo[lwb];
           35  +
           36  +  string best = (digits.substr(0,lwb.size())>=lwb ? digits.substr(0,lwb.size()) : "");
           37  +  string minSoFar = string(1, digits[0]);
           38  +  for(int t=1; t<lwb.size(); ++t) {
           39  +   if( digits[t] < lwb[0] )
           40  +   {
           41  +   }
           42  +   else if( digits[t] == lwb[0] )
           43  +   {
           44  +    string tail = digits.substr(t+1, lwb.size()-(t+1));
           45  +
           46  +    string target = lwb.substr(1, t);
           47  +    bool needOneMore = (lwb.substr(t+1) > tail);
           48  +    if(!needOneMore || incr(target)) {
           49  +     string m = minNumber(digits, target);
           50  +     if( m.size() == target.size() ) {
           51  +      string cand = digits[t] + m + tail;
           52  +      if( lwb<=cand && (best.empty() || best > cand) )
           53  +       best = cand;
           54  +     }
           55  +    }
           56  +   }
           57  +   else
           58  +   {
           59  +    string cand = digits[t] + minSoFar + digits.substr(t+1, lwb.size()-(t+1));
           60  +    if( best.empty() || best > cand )
           61  +     best = cand;
           62  +   }
           63  +
           64  +   minSoFar = min(minSoFar+digits[t], digits[t]+minSoFar);
           65  +  }
           66  +  return memo[lwb] = best;
           67  + }
           68  +
           69  + bool incr(string& s)
           70  + {
           71  +  for(int i=s.size()-1 ;; --i)
           72  +  {
           73  +   if(i==-1)
           74  +    return false;
           75  +   if(s[i]<'9') {
           76  +    s[i]++;
           77  +    break;
           78  +   }
           79  +   s[i]='0';
           80  +  }
           81  +  return true;
           82  + }
           83  +};
           84  +
           85  +// BEGIN CUT HERE
           86  +#include <ctime>
           87  +double start_time; string timer()
           88  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           89  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           90  + { os << "{ ";
           91  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           92  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           93  +void verify_case(const string& Expected, const string& Received) {
           94  + bool ok = (Expected == Received);
           95  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           97  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           98  +#define END  verify_case(_, LeftRightDigitsGame2().minNumber(digits, lowerBound));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + string digits = "565";
          103  + string lowerBound = "556";
          104  + string _ = "556";
          105  +END
          106  +CASE(1)
          107  + string digits = "565";
          108  + string lowerBound = "566";
          109  + string _ = "655";
          110  +END
          111  +CASE(2)
          112  + string digits = "565";
          113  + string lowerBound = "656";
          114  + string _ = "";
          115  +END
          116  +CASE(3)
          117  + string digits = "9876543210";
          118  + string lowerBound = "5565565565";
          119  + string _ = "5678943210";
          120  +END
          121  +CASE(4)
          122  + string digits = "8016352";
          123  + string lowerBound = "1000000";
          124  + string _ = "1086352";
          125  +END
          126  +CASE(5)
          127  + string digits = "93907757041066207580227527897335194812859183833602";
          128  + string lowerBound = "12089579919698667599337853067564506011831210501927";
          129  + string _ = "";
          130  +END
          131  +CASE(6)
          132  + string digits = "1";
          133  + string lowerBound = "2";
          134  + string _ = "";
          135  +END
          136  +CASE(6)
          137  + string digits = "2";
          138  + string lowerBound = "2";
          139  + string _ = "2";
          140  +END
          141  +CASE(6)
          142  + string digits = "3";
          143  + string lowerBound = "2";
          144  + string _ = "3";
          145  +END
          146  +CASE(6)
          147  + string digits = "55555555555555555555555555555555555555555555555555";
          148  + string lowerBound = "55555555555555555555555555555555555555555555555555";
          149  + string _ = "55555555555555555555555555555555555555555555555555";
          150  +END
          151  +}
          152  +// END CUT HERE

Added SRM/556-U/1B.cpp version [5cecb6c12f03f17c]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class XorTravelingSalesman { public:
           23  + int maxProfit(vector <int> cityValues, vector <string> roads)
           24  + {
           25  +  vector< vector<bool> > vis(cityValues.size(), vector<bool>(1024, false));
           26  +  rec(0, cityValues[0], cityValues, roads, vis);
           27  +  int best = 0;
           28  +  for(int p=0; p<cityValues.size(); ++p)
           29  +   for(int v=0; v<1024; ++v)
           30  +    if( vis[p][v] )
           31  +     best = max(best, v);
           32  +  return best;
           33  + }
           34  +
           35  + void rec(int p, int value, const vector <int>& cityValues, const vector <string>& roads,
           36  +  vector< vector<bool> >& vis)
           37  + {
           38  +  if(vis[p][value])
           39  +   return;
           40  +  vis[p][value] = true;
           41  +  for(int q=0; q<cityValues.size(); ++q)
           42  +   if(roads[p][q] == 'Y')
           43  +    rec(q, value^cityValues[q], cityValues, roads, vis);
           44  + }
           45  +};
           46  +
           47  +// BEGIN CUT HERE
           48  +#include <ctime>
           49  +double start_time; string timer()
           50  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           51  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           52  + { os << "{ ";
           53  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           54  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           55  +void verify_case(const int& Expected, const int& Received) {
           56  + bool ok = (Expected == Received);
           57  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           58  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           59  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           60  +#define END  verify_case(_, XorTravelingSalesman().maxProfit(cityValues, roads));}
           61  +int main(){
           62  +
           63  +CASE(0)
           64  + int cityValues_[] = {0, 7, 11, 5, 2};
           65  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
           66  + string roads_[] = {"NYNYY",
           67  + "YNYNN",
           68  + "NYNNN",
           69  + "YNNNN",
           70  + "YNNNN"};
           71  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
           72  + int _ = 14;
           73  +END
           74  +CASE(1)
           75  + int cityValues_[] = {556};
           76  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
           77  + string roads_[] = {"N"};
           78  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
           79  + int _ = 556;
           80  +END
           81  +CASE(2)
           82  + int cityValues_[] = {0, 4, 8, 32, 512};
           83  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
           84  + string roads_[] = {"NYYYY",
           85  + "YNNNN",
           86  + "YNNNN",
           87  + "YNNNN",
           88  + "YNNNN"};
           89  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
           90  + int _ = 556;
           91  +END
           92  +CASE(3)
           93  + int cityValues_[] = {37, 1, 19, 64, 42, 41, 64, 64, 54, 16, 256, 36, 64, 2, 4, 2, 62, 29, 58, 64, 1, 32, 16,
           94  + 256, 17, 2, 17, 4, 1, 64, 21, 8, 256, 63, 3, 1, 43, 15, 8, 39, 41, 8, 16, 8, 16, 256, 64, 512, 45, 64};
           95  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
           96  + string roads_[] = {"NNNNNNYYYYNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
           97  + "NNNNNNNNNNNNNNNNYNNNNNNNYNNNNNNNNNNNNNNNNYYNNNYYNN",
           98  + "NNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
           99  + "NNNNNNNYNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          100  + "NNNNNNNNNNNNNNNYNNYNYNNNNNNYNNNNNNNNNNYNNNNNNNNNNN",
          101  + "NNYNNNYNNNNNNNNYNNYNNNYYNNNYNYNNNNYNNNNNNNNYNNNNNN",
          102  + "YNYNNYNYNNNNNNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNYNN",
          103  + "YNNYNNYNYNYYNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNNNNNNN",
          104  + "YNNNNNNYNNNNNNNNNNNNNNYNYNNNNNNNNNNYYYNNNNNNNYNNNY",
          105  + "YNNNNNNNNNNNNNNNNYNYNYNYYNNNYNNNNYNNNNNNNNNNNNNNNY",
          106  + "NNNNNNNYNNNNYNNNNNNNNYYNNNYYNNNNYNYYNNNNNNNNNNNNNN",
          107  + "NNNNNNNYNNNNNNYNNNNYYNNNYNNYYNNNNNNNNNNNNNYNYNNNNN",
          108  + "NNNNNNNNNNYNNNNNYNNNNYNNNNNNNNNNYNYNNYNYNNNYNYNNNN",
          109  + "NNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNYNN",
          110  + "NNNNNNNNNNNYNNNNNYNYNNYYNNNNNYNNNNNNNNNYNNYNNYNNNN",
          111  + "NNNNYYYNNNNNNYNNNYYNNYNNNYNYYNNNNNNNNNYYYNNYNNYNYN",
          112  + "NYNNNNNNNNNNYNNNNNNNYNNNYYNNNYNNNNYNNNNNNNNNNNNNNN",
          113  + "NNNNNNNNNYNNNNYYNNNNNNYNNNYNNNNNYNNYNYYNNNNYNNNYNN",
          114  + "NNNYYYNNNNNNNNNYNNNNNYNYNYNNNNNNNNYNNNNNNNNNNNNNNN",
          115  + "NNNNNNNNNYNYNNYNNNNNNYNYYYNNNNNNNNNNNYNNYNNNNNYNNN",
          116  + "NNNNYNNNNNNYNNNNYNNNNYNNNYYNNNYNNNYNNNNNNNNNNYNYNY",
          117  + "NNNNNNNNNYYNYNNYNNYYYNYNNNNNNNNYNYNNNNNNNNNNYNNNNN",
          118  + "NNNNNYNNYNYNNNYNNYNNNYNNNNNNNNNNNYNNYNYNNYNNNNNNNN",
          119  + "NNNNNYNNNYNNNNYNNNYYNNNNNNNNNNNNNNNNNNNNNNYNNNYNNN",
          120  + "NYNNNNNNYYNYNNNNYNNYNNNNNNNNNNYNNNNNNYNNNYNNYNNNNN",
          121  + "NNNNNNNNNNNNNYNYYNYYYNNNNNNYNNNNNNNNNNNYYNNNNNNNYN",
          122  + "NNNNNNNNNNYNNNNNNYNNYNNNNNNNNYNNNNYNNNNNNYYNNNNYNN",
          123  + "NNNNYYNNNNYYNNNYNNNNNNNNNYNNNYYNYNNNNNNNNNNNNNNNNN",
          124  + "NNNNNNNNNYNYNNNYNNNNNNNNNNNNNYNNNNYNNNNNNNNYNNYNYN",
          125  + "NNNNNYNNNNNNNNYNYNNNNNNNNNYYYNNNNNNNNYNNNNYNNNNNNN",
          126  + "NNNNNNNNNNNNNNNNNNNNYNNNYNNYNNNNNYNNNNNNNNNNNNNNNY",
          127  + "NNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNYNNNNNNN",
          128  + "NNNNNNNNNNYNYNNNNYNNNNNNNNNYNNNYNNNYYNNNNNYNNNYNNN",
          129  + "NNNNNNNNNYNNNNNNNNNNNYYNNNNNNNYNNNNNNNYNNYNNNNNNNN",
          130  + "NNNNNYNYNNYNYNNNYNYNYNNNNNYNYNNNNNNYYNYNYNYNNNNNYN",
          131  + "YNNNNNYNYNYNNNNNNYNNNNNNNNNNNNNNYNYNNNNNYNNYNNNYNN",
          132  + "NNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNYNYNNNNNNYNNNNNNYN",
          133  + "NNNNNNNYYNNNYNNNNYNYNNNNYNNNNYNNNNNNNNNNNYNNNNYNNN",
          134  + "NNNNYNNNNNNNNYNYNYNNNNYNNNNNNNNNNYYNNNNYNNNNNNNNNY",
          135  + "NNNNNNNNNNNNYNYYNNNNNNNNNYNNNNNNNNNNNNYNNNNNYNYYNN",
          136  + "NNNNNNNNNNNNNNNYNNNYNNNNNYNNNNNNNNYYNNNNNNNNNNNNNN",
          137  + "NYNNNNNNNNNNNNNNNNNNNNYNYNYNNNNNNYNNYYNNNNNNNNNNNN",
          138  + "NYNNNNNNNNNYNNYNNNNNNNNYNNYNNYNYYNYNNNNNNNNNYNNNNN",
          139  + "NNNNNYNNNNNNYNNYNYNNNNNNNNNNYNNNNNNYNNNNNNNNNNNNNY",
          140  + "NNNNNNYNNNNYNNNNNNNNNYNNYNNNNNNNNNNNNNNYNNYNNYNNNY",
          141  + "NNNNNNNNYNNNYNYNNNNNYNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
          142  + "NYNNNNNNNNNNNNNYNNNYNNNYNNNNYNNNYNNNNYNYNNNNNNNNNN",
          143  + "NYNNNNYNNNNNNYNNNYNNYNNNNNYNNNNNNNNYNNNYNNNNNNNNNN",
          144  + "NNNNNNNNNNNNNNNYNNNNNNNNNYNNYNNNNNYNYNNNNNNNNNNNNN",
          145  + "NNNNNNNNYYNNNNNNNNNNYNNNNNNNNNYNNNNNNNYNNNNYYNNNNN"};
          146  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
          147  + int _ = 895;
          148  +END
          149  +/*
          150  +CASE(4)
          151  + int cityValues_[] = ;
          152  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
          153  + string roads_[] = ;
          154  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
          155  + int _ = ;
          156  +END
          157  +CASE(5)
          158  + int cityValues_[] = ;
          159  +   vector <int> cityValues(cityValues_, cityValues_+sizeof(cityValues_)/sizeof(*cityValues_));
          160  + string roads_[] = ;
          161  +   vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
          162  + int _ = ;
          163  +END
          164  +*/
          165  +}
          166  +// END CUT HERE

Added SRM/556-U/1C-U.cpp version [46b17adf49a4bfa2]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +template<typename T>
           23  +class IdGen
           24  +{
           25  + map<T, int> v2id_;
           26  + vector<T>   id2v_;
           27  +public:
           28  + int v2id(const T& v) {
           29  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           30  +  return v2id_[v];
           31  + }
           32  + const T& id2v(int i) const { return id2v_[i]; }
           33  + int size() const { return id2v_.size(); }
           34  +};
           35  +
           36  +template<typename Vert, typename Flow, int NV=2502>
           37  +class MaxFlow
           38  +{
           39  + IdGen<Vert> idgen;
           40  + vector<int> G[NV];
           41  + Flow F[NV][NV];
           42  +
           43  +public:
           44  + void addEdge( Vert s_, Vert t_, Flow f )
           45  + {
           46  +  const int s = idgen.v2id(s_), t = idgen.v2id(t_);
           47  +  G[s].push_back(t);
           48  +  G[t].push_back(s);
           49  +  F[s][t] = f;
           50  +  F[t][s] = 0;
           51  + }
           52  +
           53  + Flow calc( Vert s_, Vert t_ )
           54  + {
           55  +  const int S = idgen.v2id(s_), D = idgen.v2id(t_);
           56  +  for( Flow total=0 ;; ) {
           57  +   // Do BFS and compute the level for each node.
           58  +   int LV[NV] = {0};
           59  +   vector<int> Q(1, S);
           60  +   for(int lv=1; !Q.empty(); ++lv) {
           61  +    vector<int> Q2;
           62  +    for(size_t i=0; i!=Q.size(); ++i) {
           63  +     const vector<int>& ne = G[Q[i]];
           64  +     for(size_t j=0; j!=ne.size(); ++j)
           65  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           66  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           67  +    }
           68  +    Q.swap(Q2);
           69  +   }
           70  +
           71  +   // Destination is now unreachable. Done.
           72  +   if( !LV[D] )
           73  +    return total;
           74  +
           75  +   // Iterating DFS.
           76  +   bool blocked[NV] = {};
           77  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           78  +  }
           79  + }
           80  +
           81  +private:
           82  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           83  + {
           84  +  Flow flow_out = 0;
           85  +  for(size_t i=0; i!=G[v].size(); ++i) {
           86  +   int u = G[v][i];
           87  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           88  +    Flow f = min(flow_in-flow_out, F[v][u]);
           89  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           90  +     F[v][u]  -= f;
           91  +     F[u][v]  += f;
           92  +     flow_out += f;
           93  +     if( flow_in == flow_out ) return flow_out;
           94  +    }
           95  +   }
           96  +  }
           97  +  blocked[v] = (flow_out==0);
           98  +  return flow_out;
           99  + }
          100  +};
          101  +
          102  +class OldBridges { public:
          103  + string isPossible(vector <string> bridges, int a1, int a2, int an, int b1, int b2, int bn)
          104  + {
          105  +  typedef pair<int,int> Vert;
          106  +  enum {SRC, SINK, VERT, E1, E2};
          107  +  static const int INF = 99999999;
          108  +  MaxFlow<Vert, int>* mf = new MaxFlow<Vert,int>;
          109  +
          110  +  mf->addEdge(Vert(SRC,0), Vert(VERT,a1), 2*an);
          111  +  mf->addEdge(Vert(VERT,a2), Vert(SINK,0), 2*an);
          112  +  mf->addEdge(Vert(SRC,0), Vert(VERT,b1), 2*bn);
          113  +  mf->addEdge(Vert(VERT,b2), Vert(SINK,0), 2*bn);
          114  +
          115  +  int N = bridges.size();
          116  +  for(int a=0; a<N; ++a)
          117  +  for(int b=a+1; b<N; ++b)
          118  +   if(bridges[a][b] == 'N') {
          119  +    mf->addEdge(Vert(VERT,a), Vert(VERT,b), INF);
          120  +    mf->addEdge(Vert(VERT,b), Vert(VERT,a), INF);
          121  +   } else if(bridges[a][b] == 'O') {
          122  +    Vert e1 = Vert(E1, a*N+b);
          123  +    Vert e2 = Vert(E2, a*N+b);
          124  +    mf->addEdge(Vert(VERT,a), e1, 2);
          125  +    mf->addEdge(Vert(VERT,b), e1, 2);
          126  +    mf->addEdge(e1, e2, 2);
          127  +    mf->addEdge(e2, Vert(VERT,a), 2);
          128  +    mf->addEdge(e2, Vert(VERT,b), 2);
          129  +   }
          130  +
          131  +  int flow = mf->calc(Vert(SRC,0), Vert(SINK,0));
          132  +  delete mf;
          133  +  return flow==(an+an+bn+bn) ? "Yes" : "No";
          134  + }
          135  +};
          136  +
          137  +// BEGIN CUT HERE
          138  +#include <ctime>
          139  +double start_time; string timer()
          140  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          141  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          142  + { os << "{ ";
          143  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          144  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          145  +void verify_case(const string& Expected, const string& Received) {
          146  + bool ok = (Expected == Received);
          147  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          148  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          149  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          150  +#define END  verify_case(_, OldBridges().isPossible(bridges, a1, a2, an, b1, b2, bn));}
          151  +int main(){
          152  +
          153  +CASE(0)
          154  + string bridges_[] = {"XOXX","OXOX","XOXO","XXOX"};
          155  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          156  + int a1 = 0;
          157  + int a2 = 1;
          158  + int an = 1;
          159  + int b1 = 2;
          160  + int b2 = 3;
          161  + int bn = 1;
          162  + string _ = "Yes";
          163  +END
          164  +CASE(1)
          165  + string bridges_[] = {"XOXX","OXOX","XOXO","XXOX"};
          166  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          167  + int a1 = 0;
          168  + int a2 = 2;
          169  + int an = 1;
          170  + int b1 = 1;
          171  + int b2 = 3;
          172  + int bn = 1;
          173  + string _ = "No";
          174  +END
          175  +CASE(2)
          176  + string bridges_[] = {"XOXO","OXOX","XOXO","OXOX"};
          177  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          178  + int a1 = 0;
          179  + int a2 = 2;
          180  + int an = 1;
          181  + int b1 = 1;
          182  + int b2 = 3;
          183  + int bn = 1;
          184  + string _ = "Yes";
          185  +END
          186  +CASE(3)
          187  + string bridges_[] = {"XNXO","NXOX","XOXO","OXOX"};
          188  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          189  + int a1 = 0;
          190  + int a2 = 2;
          191  + int an = 1;
          192  + int b1 = 1;
          193  + int b2 = 3;
          194  + int bn = 2;
          195  + string _ = "No";
          196  +END
          197  +CASE(4)
          198  + string bridges_[] = {"XOXOO","OXOXO","XOXOO","OXOXO","OOOOX"};
          199  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          200  + int a1 = 0;
          201  + int a2 = 2;
          202  + int an = 2;
          203  + int b1 = 1;
          204  + int b2 = 3;
          205  + int bn = 2;
          206  + string _ = "Yes";
          207  +END
          208  +CASE(5)
          209  + string bridges_[] = {"XOOOX","OXOOX","OOXOX","OOOXN","XXXNX"};
          210  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          211  + int a1 = 0;
          212  + int a2 = 4;
          213  + int an = 3;
          214  + int b1 = 1;
          215  + int b2 = 2;
          216  + int bn = 2;
          217  + string _ = "No";
          218  +END
          219  +/*
          220  +CASE(6)
          221  + string bridges_[] = ;
          222  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          223  + int a1 = ;
          224  + int a2 = ;
          225  + int an = ;
          226  + int b1 = ;
          227  + int b2 = ;
          228  + int bn = ;
          229  + string _ = ;
          230  +END
          231  +CASE(7)
          232  + string bridges_[] = ;
          233  +   vector <string> bridges(bridges_, bridges_+sizeof(bridges_)/sizeof(*bridges_));
          234  + int a1 = ;
          235  + int a2 = ;
          236  + int an = ;
          237  + int b1 = ;
          238  + int b2 = ;
          239  + int bn = ;
          240  + string _ = ;
          241  +END
          242  +*/
          243  +}
          244  +// END CUT HERE