// This code checks the solutions of the inequations of Theorem 2 of // "How far away must forced letters be so that squares are still avoidable?" // It requires gmp to be installed and should be compiled with c++11 or higher and optimization O3 wich gives: // g++ check_solution.cpp -O3 -lgmp -lgmpxx -o #include #include #include using namespace std; int main(){ int n, p, sA; //we start by reading the inputs cout<<"Enter |{|w|: w in W}|, p and |A| (where A is the alphabet)"<> n>>p>>sA; vector l(n); vector f(n); for(int i=0;i>l[i]>>f[i]; if(l[i]>k) k=l[i]; } vector x(n); for(int i=0;i>x[i]; vector powSA(k+1,1); for(int i=1; i<=k; i++) powSA[i]=(sA-1)*powSA[i-1]; vector > alpha(n, vector(n,0));//we compute alpha by applying the formula for(int u=0;u > alphaBis(k+1, vector(n,0));//we compute alpha' by applying the formula for(int i=1; i<=k; i++){ for(int v=0;v beta(p+1,0);//we compute beta by dynamic programmic beta[0]=1; for(int i=1; i<=p;i++) for(int j=0; j=l[j] && beta[i-l[j]]*x[j]>beta[i]) beta[i]=beta[i-l[j]]*x[j]; bool ok = true;//we check all the inequations for(int w=0; w