USACO 2017 US Open Contest Bronze Division - The Lost Cow

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simulate the process and be careful with the casework when the direction changes.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("lostcow.in");
    ofstream cout("lostcow.out");

    int a, b;
    cin >> a >> b;

    if(a == b)
    {
        cout << 0;
        return 0;
    }

    int stp = 1;
    int total = 0;
    int dir = 1;
    int aa = a;
    while(1)
    {
        a = aa + stp * dir;
        total += (stp+stp/2);
        if(dir == 1 && a >= b && a - (stp+stp/2) * dir < b)
        {
            total -= (a-b);
            break;
        }
        if(dir == -1 && a <= b && a - (stp+stp/2) * dir > b)
        {
            total -= (b-a);
            break;
        }
        dir *= -1;
        stp *= 2;
    }

    cout << total;
    return 0;
}

with open("lostcow.in", "r") as fin:
    a, b = map(int, fin.readline().split())

if a == b:
    with open("lostcow.out", "w") as fout:
        fout.write("0")
    exit(0)

stp = 1
total = 0
dir = 1
aa = a

while True:
    a = aa + stp * dir
    total += (stp + stp // 2)
    if dir == 1 and a >= b and a - (stp + stp // 2) < b:
        total -= (a - b)
        break
    if dir == -1 and a <= b and a + (stp + stp // 2) > b:
        total -= (b - a)
        break
    dir *= -1
    stp *= 2

with open("lostcow.out", "w") as fout:
    fout.write(str(total))