Sleepy Cow Herding

Solución en video

Por Vikas Thoutam

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// Entrada y salida por archivos
	freopen("herding.in", "r", stdin);
	freopen("herding.out", "w", stdout);
 
	// Leemos las posiciones de las tres vacas, cow1, cow2 y cow3
	int cow1, cow2, cow3;
	cin >> cow1 >> cow2 >> cow3;
 
	// Ordenamos las tres posiciones, esto hará más fácil el cálculo.
	int temp;
	if (cow1 > cow3) {
		temp = cow3;
		cow3 = cow1;
		cow1 = temp;
	}
	if (cow2 > cow3) {
		temp = cow3;
		cow3 = cow2;
		cow2 = temp;
	}
	if (cow1 > cow2) {
		temp = cow2;
		cow2 = cow1;
		cow2 = temp;
	}
 
	// Calculamos la cantidad mínima de movimientos, siempre 0, 1 o 2
	int min;
	if (cow1 + 1 == cow2 &&
	    cow2 + 1 == cow3)  // En caso de que ya estén una al lado de la otra
		min = 0;
	else if (cow1 + 2 == cow2 ||
	         cow2 + 2 == cow3)  // En caso de que dos de las vacas estén a distancia uno, movemos
	                            // la otra vaca en el medio
		min = 1;
	else  // En todos los demás casos, movemos una vaca para estar en el caso else if, y luego
	      // sumamos uno para satisfacer el caso else if
		min = 2;
 
	// Calculamos la cantidad máxima de movimientos
	// El valor es simplemente uno menos que el tamaño del hueco más grande
	int maxVal = max(cow2 - cow1, cow3 - cow2) - 1;
 
	// Imprimimos tanto min como max
	printf("%d\n%d", min, maxVal);
	fclose(stdout);
}


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class SleepyCowHerding {
	public static void main(String[] args) throws IOException {
		// Entrada y salida por archivos
		BufferedReader br = new BufferedReader(new FileReader("herding.in"));
		PrintWriter pw = new PrintWriter("herding.out");
 
		// Leemos las posiciones de las tres vacas, cow1, cow2 y cow3
		StringTokenizer st = new StringTokenizer(br.readLine());
		int cow1 = Integer.parseInt(st.nextToken());
		int cow2 = Integer.parseInt(st.nextToken());
		int cow3 = Integer.parseInt(st.nextToken());
 
		// Ordenamos las tres posiciones, esto hará más fácil el cálculo.
		int temp;
		if (cow1 > cow3) {
			temp = cow3;
			cow3 = cow1;
			cow1 = temp;
		}
		if (cow2 > cow3) {
			temp = cow3;
			cow3 = cow2;
			cow2 = temp;
		}
		if (cow1 > cow2) {
			temp = cow2;
			cow2 = cow1;
			cow2 = temp;
		}
 
		// Calculamos la cantidad mínima de movimientos, siempre 0, 1 o 2
		int min;
		if (cow1 + 1 == cow2 &&
		    cow2 + 1 == cow3)  // En caso de que ya estén una al lado de la otra
			min = 0;
		else if (cow1 + 2 == cow2 ||
		         cow2 + 2 == cow3)  // En caso de que dos de las vacas estén a distancia uno,
		                            // movemos la otra vaca en el medio
			min = 1;
		else  // En todos los demás casos, movemos una vaca para estar en el caso else if, y
		      // luego sumamos uno para satisfacer el caso else if
			min = 2;
 
		// Calculamos la cantidad máxima de movimientos
		// El valor es simplemente uno menos que el tamaño del hueco más grande
		int max = Math.max(cow2 - cow1, cow3 - cow2) - 1;
 
		// Imprimimos tanto min como max
		pw.println(min);
		pw.println(max);
		pw.close();
	}
}

Pista 1

Intentemos primero encontrar el mínimo. ¿Cuántos movimientos hace falta como máximo para agrupar las vacas en ubicaciones consecutivas?

Pista 2

Ahora intentemos encontrar el máximo. Cada movimiento reduce el hueco entre los dos extremos en una cierta cantidad. Para maximizar la cantidad de pasos, basta con minimizar la cantidad de huecos reducidos después de cada movimiento.

Pista 3

Cuando hay dos vacas consecutivas, ¿cuál es la forma óptima de mover la vaca que minimiza la cantidad de huecos reducidos?

Solución

Análisis oficial (C++)

Explicación

Consideremos las posiciones de nuestras vacas como $x_1$ , $x_2$ y $x_3$ , donde $x_1 < x_2 < x_3$ .

Mínimo

Si las tres vacas ya están todas una al lado de la otra, la respuesta es $0$ .

Si dos de las vacas tienen un hueco de uno entre ellas, entonces la respuesta debe ser uno, porque la última vaca se moverá dentro del hueco (p. ej. 3, 5 y 9, donde 9 se mueve a 4).

Sin embargo, en todos los demás casos, el mínimo es 2. Esto es porque siempre podemos mover $x_1$ a $x_2 + 2$ y $x_3$ a $x_2 + 1$ en dos operaciones.

Máximo

Tendremos 2 huecos, $x_1$ a $x_2$ y $x_2$ a $x_3$ .

Después de la primera operación, uno de estos desaparecerá. La forma de maximizar la cantidad de movimientos es mantener dos vacas adyacentes en el extremo, y seguir intercambiando esas dos vacas hasta que las tres queden agrupadas en ubicaciones consecutivas.

Podemos mover uno de los extremos al otro, y seguir intercambiándolos, para obtener la cantidad máxima de movimientos. Con eso, la respuesta termina siendo $max(x_2 - x_1, x_3 - x_2) - 1$ .

Implementación

Complejidad temporal: $\mathcal{O}(1)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	freopen("herding.in", "r", stdin);
	freopen("herding.out", "w", stdout);
 
	// todas las ubicaciones de las vacas
	vector<int> a;
	for (int i = 0; i < 3; i++) {
		int b;
		cin >> b;
		a.push_back(b);
	}
	sort(a.begin(), a.end());
 
	/*
	 * La cantidad mínima de movimientos solo puede ser 0, 1 o 2.
	 * 0 es si ya son consecutivas,
	 * 1 es si hay una diferencia de 2 entre cualesquiera 2 números,
	 * y 2 es para todos los demás casos.
	 */
	if (a[0] == a[2] - 2) {
		cout << 0 << endl;
	} else if ((a[1] == a[2] - 2) || (a[0] == a[1] - 2)) {
		cout << 1 << endl;
	} else {
		cout << 2 << endl;
	}
	// el máx. es igual a la mayor diferencia entre el extremo y el medio, menos uno.
	cout << max(a[2] - a[1], a[1] - a[0]) - 1;
}


import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("herding.in"));
		PrintWriter pw = new PrintWriter(new File("herding.out"));
		int[] cows = new int[3];
		cows[0] = sc.nextInt();
		cows[1] = sc.nextInt();
		cows[2] = sc.nextInt();
		Arrays.sort(cows);
 
		// Imprimimos la cantidad mínima de movimientos
		if (cows[2] == cows[0] + 2) {
			pw.println(0);
		} else if (cows[1] == cows[0] + 2 || cows[2] == cows[1] + 2) {
			pw.println(1);
		} else {
			pw.println(2);
		}
 
		// Cantidad máxima de movimientos
		pw.println(Math.max(cows[1] - cows[0], cows[2] - cows[1]) - 1);
		pw.close();
	}
}


import sys
 
sys.stdin = open("herding.in", "r")
sys.stdout = open("herding.out", "w")
x1, x2, x3 = map(int, input().split())
 
# Mejor escenario: los tres elementos ya están en orden.
if x3 == x1 + 2:
	print(0)
	"""
	Si hay una diferencia de 2, se puede resolver en un movimiento.
	3 5 9 -> 5 7 9
	"""
elif x2 == x1 + 2 or x3 == x2 + 2:
	print(1)
	"""
	Siempre se puede resolver en dos movimientos moviendo x1 -> x3 - 2 y x2 -> x3 - 1.
	Si hay menos de un entero entre los dos elementos, se resuelve
	en el if de arriba.
	"""
else:
	print(2)
	"""
	El peor caso es incrementar de a 1 en el hueco más grande.
	3 5 9 -> 5 6 9 -> 6 7 9 -> 7 8 9
	"""
print(max(x2 - x1, x3 - x2) - 1)