fork(1) download 
  1. #include <queue>
  2. #include <map>
  3. #include <iostream>
  4.  
  5. class C {
  6. public:
  7.   /* a^b + c^d */
  8.   int a, b, c, d;
  9.  
  10. public:
  11.   C();
  12.   C(int a, int b, int c, int d);
  13.   C(const C &obj);
  14.   C &operator=(C c);
  15.   friend std::ostream &operator<<(std::ostream &s, C const &c);
  16.   friend int f(C const &c);
  17.   friend void phasenext(std::vector<C> &rv, C const &c);
  18. };
  19. C::C(){}
  20. C::C(int a, int b, int c, int d) { this->a = a; this->b = b; this->c = c; this->d = d; }
  21. C::C(const C &obj) { this->a = obj.a; this->b = obj.b; this->c = obj.c; this->d = obj.d; }
  22. C &C::operator=(C obj) { this->a = obj.a; this->b = obj.b; this->c = obj.c; this->d = obj.d; return *this; }
  23. int f(C const &c) {
  24.   int s1 = 1, s2 = 1;
  25.   for (int i = 0; i < c.b; i++) s1 *= c.a;
  26.   for (int i = 0; i < c.d; i++) s2 *= c.c;
  27.   return s1 + s2;
  28. }
  29. std::ostream &operator<<(std::ostream &s, C const &c) {
  30.   s << c.a << '^' << c.b << '+' << c.c << '^' << c.d << '=' << f(c);
  31.   return s;
  32. }
  33.  
  34. void phasenext(std::vector<C> &rv, C const &c) {
  35.   C r;
  36.   r.a = c.a + 1; r.b = c.b; r.c = c.c; r.d = c.d;
  37.   if (c.a <= c.c)
  38.     rv.push_back(r);
  39.   r.a = c.a; r.b = c.b + 1; r.c = c.c; r.d = c.d;
  40.   if (c.a <= c.c)
  41.     rv.push_back(r);
  42.   r.a = c.a; r.b = c.b; r.c = c.c + 1; r.d = c.d;
  43.   if (c.a <= c.c)
  44.     rv.push_back(r);
  45.   r.a = c.a; r.b = c.b; r.c = c.c; r.d = c.d + 1;
  46.   if (c.a <= c.c)
  47.     rv.push_back(r);
  48. }
  49.  
  50. class PriorityQueueCompare {
  51. public:
  52.   bool operator()(C const &a, C const &b) { return f(a) < f(b); }
  53. };
  54.  
  55. class MapCompare : public C {
  56. public:
  57.   bool operator()(C const &a, C const &b) {
  58.     if (a.a < b.a) return true;
  59.     if (a.a == b.a && a.b < b.b) return true;
  60.     if (a.a == b.a && a.b == b.b && a.c < b.c) return true;
  61.     if (a.a == b.a && a.b == b.b && a.c == b.c && a.d < b.d) return true;
  62.     return false;
  63.   }
  64. };
  65.  
  66. const int TARGET = 2017;
  67. int main ()
  68. {
  69.   std::priority_queue<C, std::vector<C>, PriorityQueueCompare > priority_queue;
  70.   std::map<C, int, MapCompare> map;
  71.  
  72.   C first(2, 2, 2, 2);
  73.   priority_queue.push(first);
  74.   map[first] = 1;
  75.  
  76.   while (!priority_queue.empty()) {
  77.     C got = priority_queue.top();
  78.     priority_queue.pop();
  79.  
  80.     if (f(got) == TARGET)
  81.       std::cout << got << std::endl;
  82.     if (f(got) < TARGET) {
  83.       std::vector<C> next;
  84.       phasenext(next, got);
  85.       for (std::vector<C>::iterator i = next.begin(); i != next.end(); i++) {
  86.         if (map.find(*i) == map.end()) {
  87.           map[*i] = 1;
  88.           priority_queue.push(*i);
  89.         }
  90.       }
  91. //      std::cout << "::" << got << std::endl;
  92.     }
  93.   }
  94.  
  95.   return 0;
  96. }
  97. /* end */
  98.  
Success #stdin #stdout 0s 3012KB
comments (?)
stdin 
Standard input is empty
stdout 
3^4+44^2=2017
9^2+44^2=2017
12^3+17^2=2017
https://ideone.com/2jHaUs
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 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!