#include <iostream>
#include <list>
#include <unordered_set>
using namespace std;
#include <functional>

#include <chrono>

unsigned int N = 19;

class Point{
private:
    int x, y;
public:
	Point(int a_x, int a_y)
		: x(a_x), y(a_y)
	{}
	~Point(){}

	int getX()const { return x; }
	int getY()const { return y; }

	void setX(int ax) { x = ax; }
	void setY(int ay) { y = ay; }

	bool operator == (const Point& rhs) const{
		return x == rhs.x && y == rhs.y;
	}

	bool operator != (const Point& rhs) const{
		return !(*this == rhs);
	}

	Point transpose() { return Point(y,x); }
};

namespace std
{
    // specializing hash function for Point
    template <>
    struct hash<Point>
    {
        size_t operator()(Point const & x) const /*noexcept*/ // since VS 2012 compiler doesnt support this yet
        {
            return (
                (101 + std::hash<int>()(x.getX())) *
                101 + std::hash<int>()(x.getY())
            );
        }
    };
}
class Data{
public:
    Data()
	 : m_count(0), rightBottom(0,0)
	{}

	~Data(){ m_Points.clear(); }

	// returns true if point was successfully inserted into this
	bool insert(Point p);
	size_t count();

	static bool isLegitPoint(const Point& p);

	void print();
private:
	unordered_set<Point> m_Points;
	size_t m_count;

	Point rightBottom;
};
bool Data::insert(Point p){
    if(this->m_Points.count(p))
		return false;

    this->m_Points.insert(p);

	int mul = 1;
	if(p.getX() == 0 && p.getY() == 0)
		mul = 1;
	else if(p.getX() == 0 || p.getY() == 0)
		mul = 2;
	else
		mul = 4;

	m_count += mul;

	if(p.getX() >= rightBottom.getX())
		rightBottom.setX(p.getX());

	if(p.getY() >= rightBottom.getY())
		rightBottom.setY(p.getY());


    return true;
}

size_t Data::count(){
	return this->m_count;
}

bool Data::isLegitPoint(const Point& p){
    int x = abs(p.getX());
    int y = abs(p.getY());

    unsigned int xsum, ysum;
    xsum = ysum = 0;

    while(x != 0){
        xsum += (x % 10);

        x = x / 10;
    }

    while(y != 0){
        ysum += (y % 10);

        y = y / 10;
    }

    return xsum + ysum <= N;
}

#include <fstream>
void Data::print(){
	ofstream f;
	f.open("data.txt");

	for(auto i = m_Points.begin(); i != m_Points.end(); ++i){
		f << i->getX() << "," << i->getY() << "\n";
	}

	f.close();
}


int main(){

    Point origin(0,0);

	list<Point> points;
	Data legitPoints;

    unordered_set<Point> seenPoints;
    
    auto startTime = chrono::steady_clock::now();

	points.push_back(origin);

	while(!points.empty()){
		Point p = points.front(); // this is a seek operation
        points.pop_front(); // this actually deletes an element

		// continue if p has already been checked
        if(seenPoints.count(p))
            continue;
        else
		{
            seenPoints.insert(p);
			
			if(p.getX() != p.getY())
				seenPoints.insert(p.transpose());
		}

		if(Data::isLegitPoint(p)){
			points.push_back( Point(p.getX()+1, p.getY()) );
			points.push_back( Point(p.getX(),   p.getY()+1) );

			legitPoints.insert(p);
			
			if(p.getX() != p.getY())
				legitPoints.insert(p.transpose());
		}
	}
    
    auto endTime = chrono::steady_clock::now();
    auto diff = endTime - startTime;
    
    cout << chrono::duration <double, milli> (diff).count() << " ms" << endl;
    
	cout << "Total number of points: " << legitPoints.count();
	//legitPoints.print();
	seenPoints.clear();
	return 0;
}