The lost Cow

Problems and Contests
#6

Uhmm can anybody help me?
What I thought:

John starts
1.position x on number line

2.position x-2 on number line

  1. position x + 4 on number line

This goes on till x is equal to y

When x is equal to y,
My program then counts the distance covered

What is wrong with my algorithm or in my code/?

#7

When x is exactly equal to y? What if y is say, 3?

#8

\text{I have written most of the code...uhm can you please tell me once why} x = 3 and y = 6 \text{gives use output} 9?

#9

We first go to 4, 1, then 7.
3 -> 4 = 1 unit
4 -> 1 = 3 units
1 -> 6 = 5 units
Total is 9 units of distance

#10

Could you pls elaborate it?

#11

My C++ Code:

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
  ifstream fin("lostcow.in");
  ofstream fout("lostcow.out");
  int x , y;
  fin >> x >> y;
  int distance = 0;
  int counter = 0;
  while(x != y)
  {
    counter++;
    if(counter > 1)
    {
      x++;
    }
    if(x + 1 == y)
    {
      distance++;
      fout << distance;
      break;
    }
    distance++;
    if(x - 2 == y)
    {
      distance += 2;
      fout << distance;
      break;
    }
    distance += 2;
    if(x + 4 == y)
    {
      distance += 4;
      fout << distance;
      break;
    }
    distance += 4;
  } 
}
#12

I’m not sure how I would elaborate further…

#13

I mean what we do after we get 4, 1 and 7

#14

What do you mean? We simply output the total distance travelled before Bessie is found.

#15

I am confused In this part

#16

What are you confused about?

#17

How did you get this bold thing below?

3 -> 4
4 -> 1
1 -> 6

#18

I mean, first we go from x to x+1, then from x to x-2, so 3 - 2 = 1
Then we go from x to x + 4, so 3 + 4 = 7
However, 6 is in that range, so we stop at 6.

1 Like
#19

oh ok thanks! I misunderstood the question :slight_smile:

#20

I used the method you told…this is the code I wrote but it is not giving output:

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream fin("lostcow.in");
    ofstream fout("lostcow.out");
    int x , y;
    fin >> x >> y;
    int distance = 0;
    do
    {
        distance++;
        if(x + 1 == y)
        {
            fout << distance;
            break;
        }
        distance += 2;
        if(x - 2 == y)
        {
            fout << distance;
            break;
        }
        distance += 4;
        if(x + 4 == y)
        {
            fout << distance;
            break;
        }
        x = x + 4;
    }while(x != y);

    return 0;
}
#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.