// C++17. Standard input is a sequence of little-endian 64-bit integers, // the strictly increasing base-five encodings of the proposed representatives. #include #include #include #include #include #include #include #include #include using Word = std::uint64_t; constexpr int length = 15, window = 7; constexpr int pow5[] = {1,5,25,125,625,3125,15625,78125,390625}; constexpr Word leading = 6103515625ULL; // 5^14 const int step[] = {0,1,2,1,2}; int transform(int x, int g) { return x == 0 ? 0 : 1 + ((x - 1) ^ g); } void require(bool b, const char* msg) { if (!b) throw std::runtime_error(msg); } int canonical_window(int value) { int best = value; for(int g=0;g<4;++g){ int x=value, a=0, b=0; for(int i=0;i; // state, n0, n1 (n2 = -n0-n1) std::map level{{{0,0,0},1}}; for(int i=0;i next; for(auto [s,n]:level) for(int x=0;x<5;++x){ auto t=s; t[0]=(s[0]+step[x])%3; if(x>=3){ if(s[0]<2) ++t[1+s[0]]; if(t[0]<2) --t[1+t[0]]; } next[t]+=n; } level.swap(next); } return level.at({0,0,0}); } int main(int argc,char** argv) { require(argc==2,"supply weights.txt as argument"); std::ifstream weights(argv[1]); std::string key; int val; std::map entries; while(weights >> key >> val){ require(key.size()==7 && key.find_first_not_of("01234")==std::string::npos,"bad key"); int a=std::stoi(key,nullptr,5); require(canonical_window(a)==a && entries.emplace(a,val).second,"bad orbit key"); require(std::abs(val)<=32,"weight out of bounds"); } std::vector table(pow5[7]); for(int i=0;i; std::array,2> halves; for(int m=7;m<=8;++m){ auto& h=halves[m-7]; h.resize(pow5[m]); for(int i=0;i(bytes),8)){ Word w=0; for(int i=7;i>=0;--i) w=w*256+bytes[i]; require(w<5*leading && (!n || w>prev),"range or ordering failure"); prev=w; ++n; int digits[21]={}, d=0, count[3]={}; Word z=w; for(int i=14;i>=0;--i){digits[i]=z%5;z/=5;} for(int i=0;i<15;++i){ int x=digits[i], e=(d+step[x])%3; if(x>=3){++count[d];--count[e];} d=e; } require(!d && !count[0] && !count[1],"representative is open"); std::copy(digits,digits+6,digits+15); int v=0,score=0; for(int j=0;j<6;++j) v=v*5+digits[j]; for(int j=6;j<21;++j){v=(v%pow5[6])*5+digits[j];score+=table[v];} if(score=w,"representative is not canonical"); stabilizer+=(z==w); z=(z%leading)*5+z/leading; } } require(stabilizer && 120%stabilizer==0,"bad stabilizer"); volume+=120/stabilizer; } require(std::cin.eof() && !std::cin.gcount(),"input is truncated"); require(volume==closed_count(),"orbit union misses closed words"); std::cout<<"classes "<