Coordinate Walk Program

[wangbob]

Hey guys! It's my first time here, so sorry if I don't know the rules too much. Please correct me for any errors. My problem is as follows. Given a coordinate on a grid, and starting at the origin, for each nth step, the man covers 2^n-1 units of ground in any of the four possible directions. How can we determine whether or not a point is reachable from the origin, and how to do it in the least number of steps if it is?

I'm thinking of using maybe greedy? But that would not work well as it might not be able to accurately determine the impossibility of reaching the point. Also, the greedy solution may not accurately detect impossibility and wave a possible coordinate off as impossible.

Is recursing through all the possible routes right? The maximum x and y coordinates are 10^9, so I don't know how it would run in time. I'm not quite sure how to start...

[salem c]

I guess you can start by writing out on paper what pattern you get when you do
2⁰-1 + 2¹-1 + 2²-1 + 2³-1 + ....

Then calculate the Manhattan distance to the point in question.
https://en.wikipedia.org/wiki/Taxicab_geometry

Note that this is entirely a maths problem.

Talk of "try every possible way" is the wrong way to go, because you'll almost certainly run out of time.

[lastchance]

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
   int x, y, M;
   cout << "Input x y: ";   cin >> x >> y;
   M = abs( x ) + abs( y );

   if ( M % 2 == 0 )
   {
      cout << "Impossible";
   }
   else
   {
      int n = 1;
      for ( int p2 = 2; p2 <= M; p2 *= 2 ) n++;
      cout << "Requires " << n << " steps\n";
   }
}

Input x y: 17 26
Requires 6 steps