//using the gmp library to solve the problem:// http://my.cnd.org/modules/newbb/viewtopic.php?topic_id=63219&post_id=1586759&order=1&viewmode=flat&pid=1586140&forum=2#1586759////Quote://There is an ant which can walk around on a planar grid. The ant can move one// space at a time left, right, up or down. That is, from (x, y) the ant can go// to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the// digits of the x coordinate plus the sum of the digits of the y coordinate// are greater than 25 are inaccessible to the ant. For example, the point// (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than// 25. How many points can the ant access if it starts at (1000, 1000),// including (1000, 1000) itself?//End of Quotes.//// instead of starting from (1000,1000), this program solves a modified version of// the original one. The poor ant starts from (0,0), and its// movement is limited to none negative coordinates. The limiting sum of all digits// is 25 by default, while this program accepts also larger numbers as input.//// This program uses the GMP library to do multiprecision integer computation.// you will need the free software gpm in order to test this program, and gmp is// available from http://gmplib.org//// to compile with gcc: g++ foo.cpp -o foo -lgmp -lgmpxx// to produce results for sum of digists up to 100: ./foo 100//#include<iostream>#include<cstdlib>#include<map>#include<gmpxx.h>using namespace std;class rxy {public: int x,y; rxy(void) {}; rxy(int x0, int y0) { x=x0; y=y0; };};bool fncomp(rxy lhs, rxy rhs) { return (lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y) ) ;}int f0i(int i) { int acc=0; if (i>=18) i=18; while (i>=0) { acc += 10 - abs(9 -i); i--; } return acc;}class cants {public: map<rxy,mpz_class, bool(*)(rxy,rxy)> lut; map<rxy,mpz_class, bool(*)(rxy,rxy)>::iterator iter; cants(void) { lut=map<rxy,mpz_class, bool(*)(rxy,rxy)>(fncomp); }; mpz_class block1(int level, int i) { rxy r0(level,i); iter=lut.find(r0); if (iter!=lut.end()) return(iter->second); mpz_class a0=0; if (level==0) { a0=f0i(i); return a0; } a0=0; level--; int kl0=level?i+9:i+8; if (i>=18) i=18; while (i>=0) { a0 += ( 10 - abs ( 9 - i))*block1(level,kl0-i); i--; } lut.insert(pair<rxy,mpz_class>(r0,a0)); return a0; }; mpz_class ap(int k) { return block1(k/9,k/9?k%9+1:k%9); };};int main(int argc, char *argv[]){ int kmax=25; if (argc>1) kmax=atoi(argv[1]); else cout<<"Usage:: <limiting sum>\nRunning with the default value 25 now...\n"; if ( !(kmax>=2 && kmax<=RAND_MAX)) kmax=25; cants ca0; mpz_class a0; for (int kc=2;kc<=kmax;kc++) { a0=ca0.ap(kc-2); cout<<"cutoff="<<kc<<"\t"<<a0; cout<<endl; } return 0;}