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

Added SRM/593-U/1A.cpp version [b9269837f6b290a6]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class HexagonalBoard { public:
           23  + typedef pair<int,int> vert;
           24  +
           25  + int minColors(vector <string> board)
           26  + {
           27  +  int H = board.size();
           28  +  int W = board[0].size();
           29  +
           30  +  map<vert, vector<vert>> G;
           31  +
           32  +  bool has_edge = false;
           33  +  for(int y=0; y<H; ++y)
           34  +  for(int x=0; x<W; ++x) if(board[y][x]=='X') {
           35  +   G[vert(y,x)];
           36  +   for(int Y=0; Y<H; ++Y)
           37  +   for(int X=0; X<W; ++X) if(board[Y][X]=='X')
           38  +    if(juxt(y,x,Y,X)) {
           39  +     has_edge = true;
           40  +     G[vert(y,x)].emplace_back(Y,X);
           41  +    }
           42  +  }
           43  +
           44  +  if(G.empty())
           45  +   return 0;
           46  +  if(!has_edge)
           47  +   return 1;
           48  +  return two(G) ? 2 : 3;
           49  + }
           50  +
           51  + bool juxt(int y, int x, int Y, int X)
           52  + {
           53  +  if(y==Y && x==X)
           54  +   return false;
           55  +  if(y==Y)
           56  +   return abs(x-X) == 1;
           57  +  if(y+1==Y)
           58  +   return x-1==X || x==X;
           59  +  if(Y+1==y)
           60  +   return X-1==x || X==x;
           61  +  return false;
           62  + }
           63  +
           64  + bool two(map<vert, vector<vert>>& G)
           65  + {
           66  +  map<vert, int> C;
           67  +  for(auto it=G.begin(); it!=G.end(); ++it)
           68  +   if(!C.count(it->first))
           69  +    if(!rec(it->first, G, C, 0))
           70  +     return false;
           71  +  return true;
           72  + }
           73  +
           74  + bool rec(vert v, map<vert, vector<vert>>& G, map<vert,int>& C, int c)
           75  + {
           76  +  if(C.count(v))
           77  +   return C[v] == c;
           78  +  C[v] = c;
           79  +  auto& ne = G[v];
           80  +  for(int i=0; i<ne.size(); ++i)
           81  +   if(!rec(ne[i], G, C, c^1))
           82  +    return false;
           83  +  return true;
           84  + }
           85  +};
           86  +
           87  +// BEGIN CUT HERE
           88  +#include <ctime>
           89  +double start_time; string timer()
           90  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           91  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           92  + { os << "{ ";
           93  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           94  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           95  +void verify_case(const int& Expected, const int& Received) {
           96  + bool ok = (Expected == Received);
           97  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           98  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           99  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          100  +#define END  verify_case(_, HexagonalBoard().minColors(board));}
          101  +int main(){
          102  +
          103  +CASE(0)
          104  + string board_[] = {"---",
          105  + "---",
          106  + "---"}
          107  + ;
          108  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          109  + int _ = 0;
          110  +END
          111  +CASE(1)
          112  + string board_[] = {"-X--",
          113  + "---X",
          114  + "----",
          115  + "-X--"};
          116  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          117  + int _ = 1;
          118  +END
          119  +CASE(2)
          120  + string board_[] = {"XXXX",
          121  + "---X",
          122  + "---X",
          123  + "---X"};
          124  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          125  + int _ = 2;
          126  +END
          127  +CASE(3)
          128  + string board_[] = {"XX-XX--"
          129  +,"-XX-XXX"
          130  +,"X-XX--X"
          131  +,"X--X-X-"
          132  +,"XX-X-XX"
          133  +,"-X-XX-X"
          134  +,"-XX-XX-"};
          135  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          136  + int _ = 3;
          137  +END
          138  +/*
          139  +CASE(4)
          140  + string board_[] = ;
          141  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          142  + int _ = ;
          143  +END
          144  +CASE(5)
          145  + string board_[] = ;
          146  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          147  + int _ = ;
          148  +END
          149  +*/
          150  +}
          151  +// END CUT HERE

Added SRM/593-U/1B.cpp version [a69937141079332f]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class MayTheBestPetWin { public:
           23  + int calc(vector <int> A, vector <int> B)
           24  + {
           25  +  const int N = A.size();
           26  +  vector<int> C(N);
           27  +  for(int i=0; i<N; ++i)
           28  +   C[i] = A[i] + B[i];
           29  +
           30  +  const int allmin = accumulate(A.begin(), A.end(), 0);
           31  +  const int allmax = accumulate(B.begin(), B.end(), 0);
           32  +  const int allsum = accumulate(C.begin(), C.end(), 0);
           33  +
           34  +  vector<bool> can(allsum+1);
           35  +  can[0] = true;
           36  +  for(int i=0; i<N; ++i)
           37  +   for(int k=allsum; k>=C[i]; --k)
           38  +    if(can[k-C[i]])
           39  +     can[k] = true;
           40  +
           41  +  int best = allsum;
           42  +  for(int i=0; i<=allsum; ++i)
           43  +   if(can[i])
           44  +    best = min(best, max(abs(i-allmin), abs(allmax-i)));
           45  +  return best;
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const int& Expected, const int& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, MayTheBestPetWin().calc(A, B));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + int A_[] = {3,4,4,7};
           67  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           68  + int B_[] = {3,4,4,7};
           69  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           70  + int _ = 2;
           71  +END
           72  +CASE(1)
           73  + int A_[] = {1,3,5,4,5};
           74  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           75  + int B_[] = {2,5,6,8,7};
           76  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           77  + int _ = 5;
           78  +END
           79  +CASE(2)
           80  + int A_[] = {2907,949,1674,6092,8608,5186,2630,970,1050,2415,1923,2697,5571,6941,8065,4710,716,756,5185,1341,993,5092,248,1895,4223,1783,3844,3531,2431,1755,2837,4015};
           81  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           82  + int B_[] = {7296,6954,4407,9724,8645,8065,9323,8433,1352,9618,6487,7309,9297,8999,9960,5653,4721,7623,6017,7320,3513,6642,6359,3145,7233,5077,6457,3605,2911,4679,5381,6574};
           83  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           84  + int _ = 52873;
           85  +END
           86  +/*
           87  +CASE(3)
           88  + int A_[] = ;
           89  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           90  + int B_[] = ;
           91  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           92  + int _ = ;
           93  +END
           94  +CASE(4)
           95  + int A_[] = ;
           96  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
           97  + int B_[] = ;
           98  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
           99  + int _ = ;
          100  +END
          101  +*/
          102  +}
          103  +// END CUT HERE