//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;
}