/* Solve A102508[11]. This processor hasn't a fast bit-reverser, so do everything twice, once in bit-reversed form. The bitring must have two adjacent set bits. Since it's cyclic, bit positions 0 and 1 will do. The reverse of a solution is also a solution. So, when the third bit is eliminated from position X, the last bit is eliminated from position Size+1-X. That's why solve1() is different from solve2(): it updates MaxIndex=Size+1-X. */ #include <cstdlib> #include <iostream> using namespace std; class bits128 { // std::bitset is slower (sigh) private: unsigned long long int d_lo, d_hi; // 64-bit items public: bits128(unsigned long long int loval=0) : d_lo(loval), d_hi(0) { } bool operator == (const bits128& rhs) { return (d_lo == rhs.d_lo) && (d_hi == rhs.d_hi); } bool isEmpty() const { return (d_lo == 0) && (d_hi == 0); } bits128& setbit(unsigned int ix, bool on=true) { if (on) { if (ix < 64) { d_lo |= 1ULL << ix; } else if (ix < 128) { d_hi |= 1ULL << (ix - 64); } } else { if (ix < 64) { d_lo &= ~ (1ULL << ix); } else if (ix < 128) { d_hi &= ~ (1ULL << (ix - 64)); } } } bool tstbit(unsigned int ix) const { if (ix < 64) { return ((d_lo >> ix) & 1ULL) != 0; } if (ix < 128) { return ((d_hi >> (ix - 64)) & 1ULL) != 0; } return false; } bits128& operator <<= (unsigned int sh) { if (sh > 0) { if (sh < 64) { d_hi = (d_hi << sh) | (d_lo >> (64 - sh)); d_lo <<= sh; } else if (sh < 128) { d_hi = d_lo << (sh - 64); d_lo = 0; } else { d_hi = 0; d_lo = 0; } } return *this; } bits128& operator >>= (unsigned int sh) { if (sh > 0) { if (sh < 64) { d_lo = (d_lo >> sh) | (d_hi << (64 - sh)); d_hi >>= sh; } else if (sh < 128) { d_lo = d_hi >> (sh - 64); d_hi = 0; } else { d_lo = 0; d_hi = 0; } } return *this; } bits128& operator |= (const bits128& rhs) { d_lo |= rhs.d_lo; d_hi |= rhs.d_hi; return *this; } bits128 operator << (int sh) const { bits128 res = *this; res <<= sh; return res; } bits128 operator >> (int sh) const { bits128 res = *this; res >>= sh; return res; } bits128 operator | (const bits128& rhs) const { bits128 res = *this; res |= rhs; return res; } }; static const int MaxSize = 128; typedef bits128 intset; static int Size, MaxIndex; static intset IdxSet, RevSet, DistSet, Solved; static void printIdxset() { intset set = IdxSet; for (int ix = 0; ! set.isEmpty(); ix += 1) { if (set.tstbit(0)) { cout << ' ' << ix; } set >>= 1; } } static bool solve2(int qq, int minx) { if (qq == 0) { return DistSet == Solved; } intset savedist = DistSet; for ( ; minx <= MaxIndex; minx += 1) { int rev = Size - minx; IdxSet.setbit(minx, true); RevSet.setbit(rev, true); DistSet |= IdxSet << rev; DistSet |= RevSet >> rev; if (solve2(qq - 1, minx + 1)) return true; IdxSet.setbit(minx, false); RevSet.setbit(rev, false); DistSet = savedist; } return false; } static bool solve1(int qq, int minx) { intset savedist = DistSet; for ( ; minx < Size; minx += 1) { int rev = Size - minx; MaxIndex = rev + 1; IdxSet.setbit(minx, true); RevSet.setbit(rev, true); DistSet |= IdxSet << rev; DistSet |= RevSet >> rev; if (solve2(qq - 1, minx + 1)) return true; IdxSet.setbit(minx, false); RevSet.setbit(rev, false); DistSet = savedist; } return false; } int main(int argc, const char** argv) { if (argc != 3) { cerr << "usage: " << argv[0] << " size bitquan" << endl; return 1; } Size = atoi(argv[1]); if (Size > MaxSize) { cerr << "size <= " << MaxSize << " please" << endl; return 1; } int quan = atoi(argv[2]); if (quan < 3) { cerr << "bitquan >= 3 please" << endl; return 1; } if ((quan * quan - quan + 1) < Size) { cout << "no solution: size too big" << endl; return 0; } for (int ix = 0; ix <= Size; ix += 1) { Solved.setbit(ix, true); } IdxSet = 0x3; RevSet = IdxSet << (Size - 1); DistSet = IdxSet | RevSet; if (solve1(quan - 2, 2)) { cout << "solution:"; printIdxset(); } else { cout << "no solution"; } cout << endl; return 0; }