The lost Cow

Problems and Contests
#21

perhaps you should debug by printing out the x and y values after each iteration to debug

#22

I am noticing that x and y are going in the while loop but it is not getting processed inside.

#23

I am taking a look at the official solution too below:

#include <iostream>
#include <cstdlib>

using namespace std;
typedef long long ll;

int main() {
  ll x, y;
  cin >> x >> y;

  ll ans = 0;
  ll by = 1;
  ll dir = 1;
  while(true) {
    // dir == 1 means Farmer John is moving to the right, and
    // dir == -1 means he is moving to the left.
    if((dir==1 && x<=y && y<=x+by) || (dir==-1 && x-by<=y && y<=x)) {
      // We found Bessie!
      ans += abs(y-x);
      cout << ans << endl;
      break;
    } else {
      // Didn't find Bessie! Add to our running total the cost of
      // moving 'by' units away from the start and back again.
      // Then multiply our next move's length by 2 and switch direction.
      ans += by*2;
      by *= 2;
      dir *= -1;
    }
  }
}

I am not understanding why this works.

#24

i think you’re misunderstanding the problem.

farmer john starts at position x and bessie is at position y
then farmer john travels from x to x+1,
travels from x+1 to x-2
travels from x-2 to x+4
travels from x+4 to x-8
\dots
travels from x+2^{k-1} to x-2^k
travels from x-2^k to x+2^{k+1}
(he repeats this process until he reaches bessie)

your solution only allows distances up to 4.

1 Like
#25

Thanks! I have been having trouble understanding USACO Bronze Questions because English isn’t my first language.