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

Added SRM/600-U/1A.cpp version [8f0cc3f762f50033]

            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 ORSolitaire { public:
           23  + int getMinimum(vector <int> numbers, int goal)
           24  + {
           25  +  vector<int> n2;
           26  +  for(int u: numbers)
           27  +   if((goal&u) == u)
           28  +    n2.push_back(u);
           29  +  numbers.swap(n2);
           30  +
           31  +  int best = 9999999;
           32  +  for(int v=1; v<=goal; v<<=1) if(goal&v) {
           33  +   int cnt = 0;
           34  +   for(int u: numbers)
           35  +    if(u&v)
           36  +     ++cnt;
           37  +   best = min(best, cnt);
           38  +  }
           39  +  return best;
           40  + }
           41  +};
           42  +
           43  +// BEGIN CUT HERE
           44  +#include <ctime>
           45  +double start_time; string timer()
           46  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           47  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           48  + { os << "{ ";
           49  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           50  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           51  +void verify_case(const int& Expected, const int& Received) {
           52  + bool ok = (Expected == Received);
           53  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           54  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           55  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           56  +#define END  verify_case(_, ORSolitaire().getMinimum(numbers, goal));}
           57  +int main(){
           58  +
           59  +CASE(0)
           60  + int numbers_[] = {1, 2, 4};
           61  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           62  + int goal = 7;
           63  + int _ = 1;
           64  +END
           65  +CASE(1)
           66  + int numbers_[] = {1, 2, 4, 7, 8};
           67  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           68  + int goal = 7;
           69  + int _ = 2;
           70  +END
           71  +CASE(2)
           72  + int numbers_[] = {12571295, 2174218, 2015120};
           73  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           74  + int goal = 1;
           75  + int _ = 0;
           76  +END
           77  +CASE(3)
           78  + int numbers_[] = {5,2,4,52,62,9,8,3,1,11,6};
           79  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           80  + int goal = 11;
           81  + int _ = 3;
           82  +END
           83  +CASE(4)
           84  + int numbers_[] = {503, 505, 152, 435, 491, 512, 1023, 355, 510, 500, 502, 255, 63, 508, 509, 511, 60, 250, 254, 346};
           85  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           86  + int goal = 510;
           87  + int _ = 5;
           88  +END
           89  +CASE(5)
           90  + int numbers_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
           91  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           92  + int goal = 63;
           93  + int _ = 19;
           94  +END
           95  +/*
           96  +CASE(6)
           97  + int numbers_[] = ;
           98  +   vector <int> numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_));
           99  + int goal = ;
          100  + int _ = ;
          101  +END
          102  +*/
          103  +}
          104  +// END CUT HERE

Added SRM/600-U/1B.cpp version [3ba15225dab415f3]

            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 PalindromeMatrix { public:
           23  + int minChange(vector <string> A, int rowCount, int columnCount)
           24  + {
           25  +  const int H = A.size(), W = A[0].size();
           26  +  vector<vector<int>> cpp, rpp;
           27  +  {
           28  +   vector<int> cp(W-columnCount, 0); cp.resize(W, 1);
           29  +   do cpp.push_back(cp); while(next_permutation(cp.begin(), cp.end()));
           30  +   vector<int> rp(H-rowCount, 0); rp.resize(H, 1);
           31  +   do rpp.push_back(rp); while(next_permutation(rp.begin(), rp.end()));
           32  +  }
           33  +
           34  +  int best = 99999999;
           35  +  for(auto& cp: cpp)
           36  +  {
           37  +   int c_score = 0;
           38  +   for(int x=0; x<W; ++x) if(cp[x])
           39  +    for(int y=0; y<H-1-y; ++y)
           40  +     c_score += maj(A[y][x], A[H-1-y][x]);
           41  +
           42  +   vector<int> r_score_0(H), r_score_3(H), r_score_4(H);
           43  +   for(int y=0; y<H; ++y)
           44  +    for(int x=0; x<W-1-x; ++x)
           45  +     if(!cp[x] && !cp[W-1-x]) {
           46  +      r_score_0[y] += maj(A[y][x], A[y][W-1-x]);
           47  +      r_score_3[y] += maj(A[y][x], A[y][W-1-x]);
           48  +      r_score_4[y] += maj(A[y][x], A[y][W-1-x]);
           49  +     } else {
           50  +      if(cp[x] && cp[W-1-x])
           51  +       r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x])
           52  +        - maj(A[y][x],A[H-1-y][x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]);
           53  +      else if(cp[x])
           54  +       r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x]) - maj(A[y][x],A[H-1-y][x]);
           55  +      else
           56  +       r_score_3[y] += maj(A[y][x],A[H-1-y][W-1-x],A[y][W-1-x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]);
           57  +      r_score_4[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x])
           58  +       - (cp[x] ? maj(A[y][x],A[H-1-y][x]) : 0) - (cp[W-1-x] ? maj(A[y][W-1-x],A[H-1-y][W-1-x]) : 0);
           59  +     }
           60  +
           61  +   for(auto& rp: rpp) {
           62  +    int score = c_score;
           63  +    for(int y=0; y<H; ++y) if(rp[y]) {
           64  +     if(!rp[H-1-y]) score += r_score_3[y];
           65  +     else score += (y<H-1-y ? r_score_4 : r_score_0)[y];
           66  +    }
           67  +    best = min(best, score);
           68  +   }
           69  +  }
           70  +  return best;
           71  + }
           72  +
           73  + static int maj(char a, char b, char c, char d) {
           74  +  int cnt = (a=='0')+(b=='0')+(c=='0')+(d=='0');
           75  +  return cnt<2?cnt:4-cnt;
           76  + }
           77  + static int maj(char a, char b, char c) {
           78  +  int cnt = (a=='0')+(b=='0')+(c=='0');
           79  +  return cnt<2?cnt:3-cnt;
           80  + }
           81  + static int maj(char a, char b) {
           82  +  return a!=b;
           83  + }
           84  +};
           85  +
           86  +// BEGIN CUT HERE
           87  +#include <ctime>
           88  +double start_time; string timer()
           89  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           90  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           91  + { os << "{ ";
           92  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           93  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           94  +void verify_case(const int& Expected, const int& Received) {
           95  + bool ok = (Expected == Received);
           96  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           97  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           98  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           99  +#define END  verify_case(_, PalindromeMatrix().minChange(A, rowCount, columnCount));}
          100  +int main(){
          101  +
          102  +CASE(0)
          103  + string A_[] = {"0000"
          104  +,"1000"
          105  +,"1100"
          106  +,"1110"};
          107  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          108  + int rowCount = 2;
          109  + int columnCount = 2;
          110  + int _ = 1;
          111  +END
          112  +CASE(1)
          113  + string A_[] = {"0000"
          114  +,"1000"
          115  +,"1100"
          116  +,"1110"};
          117  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          118  + int rowCount = 3;
          119  + int columnCount = 2;
          120  + int _ = 3;
          121  +END
          122  +CASE(2)
          123  + string A_[] = {"01"
          124  +,"10"};
          125  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          126  + int rowCount = 1;
          127  + int columnCount = 1;
          128  + int _ = 1;
          129  +END
          130  +CASE(3)
          131  + string A_[] = {"1110"
          132  +,"0001"};
          133  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          134  + int rowCount = 0;
          135  + int columnCount = 0;
          136  + int _ = 0;
          137  +END
          138  +CASE(4)
          139  + string A_[] = {"01010101"
          140  +,"01010101"
          141  +,"01010101"
          142  +,"01010101"
          143  +,"01010101"
          144  +,"01010101"
          145  +,"01010101"
          146  +,"01010101"};
          147  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          148  + int rowCount = 2;
          149  + int columnCount = 3;
          150  + int _ = 8;
          151  +END
          152  +CASE(5)
          153  + string A_[] = {"000000000000"
          154  +,"011101110111"
          155  +,"010001010101"
          156  +,"010001010101"
          157  +,"011101010101"
          158  +,"010101010101"
          159  +,"010101010101"
          160  +,"011101110111"
          161  +,"000000000000"
          162  +,"000000000000"};
          163  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          164  + int rowCount = 5;
          165  + int columnCount = 9;
          166  + int _ = 14;
          167  +END
          168  +CASE(6)
          169  + string A_[] = {"11111101001110"
          170  +,"11000111111111"
          171  +,"00010101111001"
          172  +,"10110000111111"
          173  +,"10000011010010"
          174  +,"10001101101101"
          175  +,"00101010000001"
          176  +,"10111010100100"
          177  +,"11010011110111"
          178  +,"11100010110110"
          179  +,"00100101010100"
          180  +,"01001011001000"
          181  +,"01010001111010"
          182  +,"10100000010011"};
          183  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          184  + int rowCount = 6;
          185  + int columnCount = 8;
          186  + int _ = 31;
          187  +END
          188  +/*
          189  +CASE(7)
          190  + string A_[] = ;
          191  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          192  + int rowCount = ;
          193  + int columnCount = ;
          194  + int _ = ;
          195  +END
          196  +CASE(8)
          197  + string A_[] = ;
          198  +   vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
          199  + int rowCount = ;
          200  + int columnCount = ;
          201  + int _ = ;
          202  +END
          203  +*/
          204  +}
          205  +// END CUT HERE