The Lost Cow

Explicación

En cada paso, vemos de dónde parte Farmer John y hacia dónde intenta ir. Si su camino no se superpone con el de Bessie, sumamos la distancia que recorre a un total acumulado y lo movemos a su posición inicial. Por otro lado, si su camino se superpone de alguna forma con el de Bessie, solo sumamos al total su distancia hasta Bessie.

Implementación

Complejidad temporal: $\mathcal{O}(\log|x - y|)$

Demostración

Digamos que la distancia entre Farmer John y Bessie es $D = |x - y|$ . En cada paso, Farmer John recorre el doble de la distancia que recorrió en el paso anterior: $1, 2, 4, 8, 16, \cdots$ . Se ve cómo la distancia crece de forma exponencial.

Farmer John encontrará a Bessie cuando el rango de su movimiento incluya su posición. Esto ocurre cuando la distancia que recorre en un solo paso, $2^k$ , es al menos $D$ .

Matemáticamente, esto significa $2^k \ge D \implies k \ge \log_2 D$ .

Así, la cantidad de pasos necesarios para encontrar a Bessie es proporcional a $\log_2(D)$ , y esa es la complejidad temporal total.

C++JavaPython


#include <fstream>
#include <iostream>
 
int main() {
	std::ifstream read("lostcow.in");
	int x, y;
	read >> x >> y;
 
	int dir = 1;
	int total_distance = 0;
	int dir_distance = 1;
	while (true) {
		if ((dir == 1 && x <= y && y <= (x + dir_distance)) ||
		    (dir == -1 && y <= x && (x - dir_distance) <= y)) {
			// encontramos a bessie
			total_distance += std::abs(y - x);  // distancia hasta ella
			std::ofstream("lostcow.out") << total_distance << std::endl;
			break;
		} else {
			// todavía no encontramos a bessie
			total_distance += dir_distance * 2;
			dir_distance *= 2;  // duplicamos la distancia
			dir *= -1;          // cambiamos de dirección
		}
	}
}


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;
		int totalDistance = 0;
		int dirDistance = 1;
		while (true) {
			if ((dir == 1 && x <= y && y <= (x + dirDistance)) ||
			    (dir == -1 && y <= x && (x - dirDistance <= y))) {
				// encontramos a bessie
				totalDistance += Math.abs(y - x);  // distancia hasta ella
				io.println(totalDistance);
				break;
			} else {
				// todavía no encontramos a bessie
				totalDistance += (dirDistance * 2);
				dirDistance *= 2;  // duplicamos la distancia
				dir *= -1;         // cambiamos de dirección
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


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)
	):
		# encontramos a bessie
		total_distance += abs(y - x)  # distancia hasta ella
		print(total_distance, file=open("lostcow.out", "w"))
		break
	else:
		# todavía no encontramos a bessie
		total_distance += dir_distance * 2
		dir_distance *= 2  # duplicamos la distancia
		dir_ *= -1  # cambiamos de dirección