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

Added SRM/596-U/1A.cpp version [c682955937bb1876]

            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 IncrementAndDoubling { public:
           23  + int getMin(vector <int> d)
           24  + {
           25  +  int cnt = 0;
           26  +  for(;;++cnt)
           27  +  {
           28  +   for(auto& di : d)
           29  +    if(di%2 == 1)
           30  +     ++cnt, di--;
           31  +   if(count(d.begin(), d.end(), 0) == d.size())
           32  +    break;
           33  +   for(auto& di : d)
           34  +    di /= 2;
           35  +  }
           36  +  return cnt;
           37  + }
           38  +};
           39  +
           40  +// BEGIN CUT HERE
           41  +#include <ctime>
           42  +double start_time; string timer()
           43  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           44  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           45  + { os << "{ ";
           46  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           47  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           48  +void verify_case(const int& Expected, const int& Received) {
           49  + bool ok = (Expected == Received);
           50  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           51  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           52  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           53  +#define END  verify_case(_, IncrementAndDoubling().getMin(desiredArray));}
           54  +int main(){
           55  +
           56  +CASE(0)
           57  + int desiredArray_[] = {2, 1};
           58  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           59  + int _ = 3;
           60  +END
           61  +CASE(1)
           62  + int desiredArray_[] = {16, 16, 16};
           63  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           64  + int _ = 7;
           65  +END
           66  +CASE(2)
           67  + int desiredArray_[] = {100};
           68  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           69  + int _ = 9;
           70  +END
           71  +CASE(3)
           72  + int desiredArray_[] = {0, 0, 1, 0, 1};
           73  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           74  + int _ = 2;
           75  +END
           76  +CASE(4)
           77  + int desiredArray_[] = {123, 234, 345, 456, 567, 789};
           78  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           79  + int _ = 40;
           80  +END
           81  +CASE(5)
           82  + int desiredArray_[] = {7,5,8,1,8,6,6,5,3,5,5,2,8,9,9,4,6,9,4,4,1,9,9,2,8,4,7,4,8,8,6,3,9,4,3,4,5,1,9,8,3,8,3,7,9,3,8,4,4,7};
           83  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           84  + int _ = 84;
           85  +END
           86  +/*
           87  +CASE(6)
           88  + int desiredArray_[] = ;
           89  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           90  + int _ = ;
           91  +END
           92  +CASE(7)
           93  + int desiredArray_[] = ;
           94  +   vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredArray_)/sizeof(*desiredArray_));
           95  + int _ = ;
           96  +END
           97  +*/
           98  +}
           99  +// END CUT HERE

Added SRM/596-U/1B.cpp version [0026c7bfbd49720a]

            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 BitwiseAnd { public:
           23  + vector<long long> lexSmallest(vector<long long> subset, int N)
           24  + {
           25  +  vector<LL> FAIL;
           26  +
           27  +  // precheck
           28  +  for(int i=0; i<subset.size(); ++i)
           29  +  for(int j=i+1; j<subset.size(); ++j)
           30  +   if((subset[i]&subset[j])==0)
           31  +    return FAIL;
           32  +  for(int i=0; i<subset.size(); ++i)
           33  +  for(int j=i+1; j<subset.size(); ++j)
           34  +  for(int k=j+1; k<subset.size(); ++k)
           35  +   if((subset[i]&subset[j]&subset[k])!=0)
           36  +    return FAIL;
           37  +
           38  +  vector<LL> ans = subset;
           39  +
           40  +  LL rest = (1LL<<60)-1;
           41  +  vector<LL> leftbits = subset;
           42  +  for(int i=0; i<subset.size(); ++i)
           43  +  {
           44  +   rest &= ~subset[i];
           45  +   for(int k=0; k<leftbits.size(); ++k) if(k!=i)
           46  +    leftbits[k] &= ~ subset[i];
           47  +  }
           48  +
           49  +  while(leftbits.size() < N)
           50  +  {
           51  +   LL v = 0;
           52  +   for(int i=0; i<leftbits.size(); ++i)
           53  +   {
           54  +    if(leftbits[i] == 0)
           55  +     return FAIL;
           56  +    LL least = 1;
           57  +    while((leftbits[i] & least)==0)
           58  +     least <<= 1;
           59  +    leftbits[i] &= ~least;
           60  +    v |= least;
           61  +   }
           62  +
           63  +   LL restv = 0;
           64  +   int needbits = (N - leftbits.size() - 1);
           65  +   while(needbits--) {
           66  +    if(rest == 0)
           67  +     return FAIL;
           68  +    LL least = 1;
           69  +    while((rest & least)==0)
           70  +     least <<= 1;
           71  +    rest &= ~least;
           72  +    restv |= least;
           73  +   }
           74  +
           75  +   leftbits.push_back(restv);
           76  +   ans.push_back(v | restv);
           77  +  }
           78  +
           79  +  sort(ans.begin(), ans.end());
           80  +  return ans;
           81  + }
           82  +};
           83  +
           84  +// BEGIN CUT HERE
           85  +#include <ctime>
           86  +double start_time; string timer()
           87  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           88  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           89  + { os << "{ ";
           90  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           91  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           92  +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
           93  + bool ok = (Expected == Received);
           94  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           95  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           96  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           97  +#define END  verify_case(_, BitwiseAnd().lexSmallest(subset, N));}
           98  +int main(){
           99  +
          100  +CASE(0)
          101  + long long subset_[] = {14, 20};
          102  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          103  + int N = 3;
          104  + long long __[] = {14, 18, 20 };
          105  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          106  +END
          107  +CASE(1)
          108  + long long subset_[] = {11, 17, 20};
          109  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          110  + int N = 4;
          111  + vector<long long> _;
          112  +END
          113  +CASE(2)
          114  + long long subset_[] = {99, 157};
          115  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          116  + int N = 4;
          117  + long long __[] = {99, 157, 262, 296 };
          118  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          119  +END
          120  +CASE(3)
          121  + long long subset_[] = {1152921504606846975};
          122  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          123  + int N = 3;
          124  + vector<long long> _;
          125  +END
          126  +CASE(4)
          127  + vector<long long> subset;
          128  + int N = 5;
          129  + long long __[] = {15, 113, 402, 676, 840 };
          130  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          131  +END
          132  +CASE(5)
          133  + long long subset_[] = {1, 3, 5, 7, 9, 11};
          134  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          135  + int N = 6;
          136  + vector<long long> _;
          137  +END
          138  +CASE(6)
          139  +    long long subset_[] = {(1LL<<60)-1>>50<<50};
          140  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          141  + int N = 11;
          142  +    vector<long long> _;
          143  +END
          144  +/*
          145  +CASE(7)
          146  + long long subset_[] = ;
          147  +   vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subset_));
          148  + int N = ;
          149  + long long __[] = ;
          150  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE