USACO Bronze 2017 Open - The Lost Cow

Authors: Jesse Choe, Ananth Kashyap, Brad Ma, Rameez Parwez

Appears In

Bronze - Simulation

Explanation

At each step, we check where Farmer John starts and where he's trying to go. If his path doesn't overlap with Bessie's path, we add the distance he convers to a running total and move him to his starting position. On the other hand, if his path somehow overlaps with Bessie's, we add only his distance from Bessie to the total.

Implementation

Time Complexity: $\mathcal{O}(\log|x - y|)$

Proof

C++

#include <fstream>
#include <iostream>

int main() {
	std::ifstream read("lostcow.in");
	int x, y;
	read >> x >> y;

	int dir = 1;
	int total_distance = 0;

Java

import java.io.*;
import java.util.StringTokenizer;

public class TheLostCow {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("lostcow");
		int x = io.nextInt();
		int y = io.nextInt();

		int dir = 1;

Python

with open("lostcow.in") as read:
	x, y = [int(i) for i in read.readline().split()]

dir_ = 1
total_distance = 0
dir_distance = 1
while True:
	if (dir_ == 1 and x <= y and y <= (x + dir_distance)) or (
		dir_ == -1 and y <= x and (x - dir_distance <= y)
	):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!