/* Topcoder SRM 604, D2, 500-Pointer (PowerOfThreeEasy) James S. Plank Thu Sep 15 16:14:12 EDT 2016 */ #include #include #include #include #include using namespace std; class PowerOfThreeEasy { public: string ableToGet(int x, int y); }; string PowerOfThreeEasy::ableToGet(int x, int y) { vector TheSet; /* This will hold the elements of the set. */ long long d, sum; int i, j; if (x == 0 && y == 0) return "Possible"; /* First, calculate TheSet. The elements here are successive powers of three such that their sum equals x+y. */ d = 1; sum = 0; do { TheSet.push_back(d); sum += d; d *= 3; } while (sum < x + y); /* When we get to this point, either sum > x+y, which means that it's impossible, or sum = x+y, and we can move onto the enumeration. */ if (sum != x + y) return "Impossible"; /* Do the power set enumeration. For each subset of TheSet, add up the elements of the subset. If they equal x, then it's "Possible" and you can return. Otherwise, try the next subset. */ for (i = 0; i < (1 << TheSet.size()); i++) { sum = 0; for (j = 0; j < TheSet.size(); j++) { if (i & (1 << j)) sum += TheSet[j]; } if (sum == x) return "Possible"; } /* If we couldn't find a subset, then return "Impossible". */ return "Impossible"; }