fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3. #include <unordered_set>
  4. using namespace std;
  5. #include <functional>
  6.  
  7. #include <chrono>
  8.  
  9. unsigned int N = 19;
  10.  
  11. class Point{
  12. private:
  13.     int x, y;
  14. public:
  15. 	Point(int a_x, int a_y)
  16. 		: x(a_x), y(a_y)
  17. 	{}
  18. 	~Point(){}
  19.  
  20. 	int getX()const { return x; }
  21. 	int getY()const { return y; }
  22.  
  23. 	void setX(int ax) { x = ax; }
  24. 	void setY(int ay) { y = ay; }
  25.  
  26. 	bool operator == (const Point& rhs) const{
  27. 		return x == rhs.x && y == rhs.y;
  28. 	}
  29.  
  30. 	bool operator != (const Point& rhs) const{
  31. 		return !(*this == rhs);
  32. 	}
  33.  
  34. 	Point transpose() { return Point(y,x); }
  35. };
  36.  
  37. namespace std
  38. {
  39.     // specializing hash function for Point
  40.     template <>
  41.     struct hash<Point>
  42.     {
  43.         size_t operator()(Point const & x) const /*noexcept*/ // since VS 2012 compiler doesnt support this yet
  44.         {
  45.             return (
  46.                 (101 + std::hash<int>()(x.getX())) *
  47.                 101 + std::hash<int>()(x.getY())
  48.             );
  49.         }
  50.     };
  51. }
  52. class Data{
  53. public:
  54.     Data()
  55. 	 : m_count(0), rightBottom(0,0)
  56. 	{}
  57.  
  58. 	~Data(){ m_Points.clear(); }
  59.  
  60. 	// returns true if point was successfully inserted into this
  61. 	bool insert(Point p);
  62. 	size_t count();
  63.  
  64. 	static bool isLegitPoint(const Point& p);
  65.  
  66. 	void print();
  67. private:
  68. 	unordered_set<Point> m_Points;
  69. 	size_t m_count;
  70.  
  71. 	Point rightBottom;
  72. };
  73. bool Data::insert(Point p){
  74.     if(this->m_Points.count(p))
  75. 		return false;
  76.  
  77.     this->m_Points.insert(p);
  78.  
  79. 	int mul = 1;
  80. 	if(p.getX() == 0 && p.getY() == 0)
  81. 		mul = 1;
  82. 	else if(p.getX() == 0 || p.getY() == 0)
  83. 		mul = 2;
  84. 	else
  85. 		mul = 4;
  86.  
  87. 	m_count += mul;
  88.  
  89. 	if(p.getX() >= rightBottom.getX())
  90. 		rightBottom.setX(p.getX());
  91.  
  92. 	if(p.getY() >= rightBottom.getY())
  93. 		rightBottom.setY(p.getY());
  94.  
  95.  
  96.     return true;
  97. }
  98.  
  99. size_t Data::count(){
  100. 	return this->m_count;
  101. }
  102.  
  103. bool Data::isLegitPoint(const Point& p){
  104.     int x = abs(p.getX());
  105.     int y = abs(p.getY());
  106.  
  107.     unsigned int xsum, ysum;
  108.     xsum = ysum = 0;
  109.  
  110.     while(x != 0){
  111.         xsum += (x % 10);
  112.  
  113.         x = x / 10;
  114.     }
  115.  
  116.     while(y != 0){
  117.         ysum += (y % 10);
  118.  
  119.         y = y / 10;
  120.     }
  121.  
  122.     return xsum + ysum <= N;
  123. }
  124.  
  125. #include <fstream>
  126. void Data::print(){
  127. 	ofstream f;
  128. 	f.open("data.txt");
  129.  
  130. 	for(auto i = m_Points.begin(); i != m_Points.end(); ++i){
  131. 		f << i->getX() << "," << i->getY() << "\n";
  132. 	}
  133.  
  134. 	f.close();
  135. }
  136.  
  137.  
  138. int main(){
  139.  
  140.     Point origin(0,0);
  141.  
  142. 	list<Point> points;
  143. 	Data legitPoints;
  144.  
  145.     unordered_set<Point> seenPoints;
  146.  
  147.     auto startTime = chrono::steady_clock::now();
  148.  
  149. 	points.push_back(origin);
  150.  
  151. 	while(!points.empty()){
  152. 		Point p = points.front(); // this is a seek operation
  153.         points.pop_front(); // this actually deletes an element
  154.  
  155. 		// continue if p has already been checked
  156.         if(seenPoints.count(p))
  157.             continue;
  158.         else
  159. 		{
  160.             seenPoints.insert(p);
  161.  
  162. 			if(p.getX() != p.getY())
  163. 				seenPoints.insert(p.transpose());
  164. 		}
  165.  
  166. 		if(Data::isLegitPoint(p)){
  167. 			points.push_back( Point(p.getX()+1, p.getY()) );
  168. 			points.push_back( Point(p.getX(),   p.getY()+1) );
  169.  
  170. 			legitPoints.insert(p);
  171.  
  172. 			if(p.getX() != p.getY())
  173. 				legitPoints.insert(p.transpose());
  174. 		}
  175. 	}
  176.  
  177.     auto endTime = chrono::steady_clock::now();
  178.     auto diff = endTime - startTime;
  179.  
  180.     cout << chrono::duration <double, milli> (diff).count() << " ms" << endl;
  181.  
  182. 	cout << "Total number of points: " << legitPoints.count();
  183. 	//legitPoints.print();
  184. 	seenPoints.clear();
  185. 	return 0;
  186. }
Success #stdin #stdout 0.02s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16.2118 ms
Total number of points: 102485
https://ideone.com/5IwYkP
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!