Hoofball

Pistas

Pista 1

Juguemos con la entrada de ejemplo y dibujemos otros casos.

Pista 2

¿Cuándo queda una pelota atrapada en un bucle infinito?

Solución

Análisis oficial (C++)

Solución

Explicación

Primero, nos damos cuenta de que Farmer John necesitará otra pelota en uno de dos casos:

Una vaca es una vaca fuente, o sea, una vaca a la que Farmer John le pasa primero.
Dos vacas están cerca, así que se pasan una pelota de un lado a otro sin fin y se necesita otra pelota para que otras vacas la tengan.

Entonces, cada vez que ocurre esto lo contamos y devolvemos ese conteo total como respuesta cuando terminamos. Podemos hacerlo primero encontrando a qué vaca, si es que hay alguna, le pasa la pelota cada vaca.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

PythonC++Java


import sys
 
sys.stdin = open("hoofball.in", "r")
sys.stdout = open("hoofball.out", "w")
 
n = int(input())
cows = sorted(list(map(int, input().strip().split())))
balls = [0] * n
ans = 0
 
 
def nearestneighbor(ind):
	lnbr, rnbr = -1, -1
	ldist, rdist = 1000, 1000
	for i in range(n):
		"""
		Si la vaca que estamos mirando está a la izquierda
		y está más cerca del objetivo que la anterior.
		"""
		if cows[i] < cows[ind] and cows[ind] - cows[i] < ldist:
			lnbr = i
			ldist = cows[ind] - cows[i]
	for i in range(n):
		# lo mismo, pero para la derecha.
		if cows[i] > cows[ind] and cows[i] - cows[ind] < rdist:
			rnbr = i
			rdist = cows[i] - cows[ind]
	return lnbr if ldist <= rdist else rnbr
 
 
for i in range(n):
	# todas las vacas que reciben una pelota
	balls[nearestneighbor(i)] += 1
for i in range(n):
	"""
	si ninguna de las vecinas le pasa la pelota a esta vaca,
	entonces hay que darle una pelota.
	"""
	if balls[i] == 0:
		ans += 1
	"""
	Si encontramos dos vacas que solo se pasan entre sí,
	también hay que darles una.
	"""
	if (
		i < nearestneighbor(i)
		and nearestneighbor(nearestneighbor(i)) == i
		and balls[i] == 1
		and balls[nearestneighbor(i)] == 1
	):
		ans += 1
 
print(ans)


#include <fstream>
#include <iostream>
using namespace std;
 
const int MAX_N = 100;
const int MAX_X = 1000;
 
 
int N, cows[MAX_N], cowsPassingTo[MAX_N];
 
// ¿A qué vaca le pasa una vaca dada?
int passToCow(int cow) {
	int leftCow = -1;
	int rightCow = -1;
	int leftRange = MAX_X;
	int rightRange = MAX_X;
	// Para cada vaca, encontramos las vacas más cercanas a su izquierda y a su derecha
	for (int i = 0; i < N; i++) {
		if (cows[i] < cows[cow] && cows[cow] - cows[i] < leftRange) {
			leftCow = i;
			leftRange = cows[cow] - cows[i];
		}
		if (cows[i] > cows[cow] && cows[i] - cows[cow] < rightRange) {
			rightCow = i;
			rightRange = cows[i] - cows[cow];
		}
	}
 
	// Devolvemos el identificador de posición de la vaca a la que le pasa la vaca dada
	if (leftRange <= rightRange) { return leftCow; }
	return rightCow;
}
 
int main() {
	ifstream fin("hoofball.in");
	ofstream fout("hoofball.out");
	fin >> N;
	int ballsNeeded = 0;
	for (int i = 0; i < N; i++) { fin >> cows[i]; }
	for (int i = 0; i < N; i++) { cowsPassingTo[passToCow(i)]++; }
	for (int i = 0; i < N; i++) {
		// Esta es una vaca fuente, así que le damos una pelota
		if (cowsPassingTo[i] == 0) { ballsNeeded++; }
		// Esta vaca solo le pasa a 1 otra vaca para siempre, así que le damos una pelota
		if (i < passToCow(i) && passToCow(passToCow(i)) == i && cowsPassingTo[i] == 1 &&
		    cowsPassingTo[passToCow(i)] == 1) {
			ballsNeeded++;
		}
	}
	fout << ballsNeeded << "\n";
}


import java.io.*;
import java.util.*;
 
public class Hoofball {
	static final int MAX_X = 1000;
 
	static int N;
	static int[] cows;
	static int[] cowsPassingTo;
 
	// ¿A qué vaca le pasa una vaca dada?
	public static int passToCow(int cow) {
		int leftCow = -1;
		int rightCow = -1;
		int leftRange = MAX_X;
		int rightRange = MAX_X;
 
		// Para cada vaca, encontramos las vacas más cercanas a su izquierda y a su derecha
		for (int i = 0; i < N; i++) {
			if (cows[i] < cows[cow] && cows[cow] - cows[i] < leftRange) {
				leftCow = i;
				leftRange = cows[cow] - cows[i];
			}
			if (cows[i] > cows[cow] && cows[i] - cows[cow] < rightRange) {
				rightCow = i;
				rightRange = cows[i] - cows[cow];
			}
		}
 
		// Devolvemos el identificador de posición de la vaca a la que le pasa la vaca dada
		if (leftRange <= rightRange) { return leftCow; }
		return rightCow;
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("hoofball");
 
		N = io.nextInt();
		cows = new int[N];
		cowsPassingTo = new int[N];
		int ballsNeeded = 0;
 
		for (int i = 0; i < N; i++) { cows[i] = io.nextInt(); }
 
		// Clasificamos cada vaca
		for (int i = 0; i < N; i++) { cowsPassingTo[passToCow(i)]++; }
 
		for (int i = 0; i < N; i++) {
			// Esta es una vaca fuente, así que le damos una pelota
			if (cowsPassingTo[i] == 0) { ballsNeeded++; }
			// Esta vaca solo le pasa a 1 otra vaca para siempre, así que le damos una pelota
			if (i < passToCow(i) && passToCow(passToCow(i)) == i &&
			    cowsPassingTo[i] == 1 && cowsPassingTo[passToCow(i)] == 1) {
				ballsNeeded++;
			}
		}
 
		io.println(ballsNeeded);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Solución en video

Por Arpan Banerjee

Video de YouTube (kRHzaBuWw9g)

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int n, cows[100], reach[100], to[100];
 
// reach[i] es cuántas vacas le pasan la pelota a la vaca i
// to[i] es a dónde le pasa la pelota la vaca i
 
int main() {
	ifstream cin("hoofball.in");
	ofstream cout("hoofball.out");
	cin >> n;
	for (int i = 0; i < n; i++) cin >> cows[i];
	if (n <= 2) {
		cout << 1 << endl;
		return 0;
	}
	sort(cows, cows + n);  // O(nlogn)
	reach[1]++;
	reach[n - 2]++;
	to[0] = 1;
	to[n - 1] = n - 2;
	for (int i = 1; i < n - 1; i++) {
		if (cows[i] - cows[i - 1] <= cows[i + 1] - cows[i]) {
			reach[i - 1]++;
			to[i] = i - 1;
		} else {
			reach[i + 1]++;
			to[i] = i + 1;
		}
	}
	int num_islands = 0;
	if (reach[0] == 1 && reach[1] == 1 && to[2] != 1) num_islands++;
	if (reach[n - 1] == 1 && reach[n - 2] == 1 && to[n - 3] != n - 2) num_islands++;
 
	for (int i = 2; i < n - 3; i++) {
		if (reach[i] == 1 && reach[i + 1] == 1 && to[i + 2] != i + 1 &&
		    to[i - 1] != i) {
			num_islands++;
		}
	}
	cout << count(reach, reach + n, 0) + num_islands << endl;
}


import java.io.*;
import java.util.*;
 
class Main {
	static BufferedReader in;
	static PrintWriter out;
	static {
		try {
			in = new BufferedReader(new FileReader("hoofball.in"));
			out = new PrintWriter(new FileWriter("hoofball.out"));
		} catch (IOException e) {}
	}
	public static void main(String[] args) throws IOException {
 
		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int[] cows = new int[n];
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < n; i++) { cows[i] = Integer.parseInt(st.nextToken()); }
		in.close();
		if (n <= 2) {
			out.write(1);
			System.exit(0);
		}
		Arrays.sort(cows);
		int[] reach = new int[n];  // reach[i] es cuántas vacas le pasan la pelota a i
		int[] to = new int[n];     // to[i] es a dónde le pasa la pelota la vaca i
		reach[1]++;
		reach[n - 2]++;
		to[0] = 1;
		to[n - 1] = n - 2;
		for (int i = 1; i < n - 1; i++) {
			if (cows[i] - cows[i - 1] <= cows[i + 1] - cows[i]) {
				reach[i - 1]++;
				to[i] = i - 1;
			} else {
				reach[i + 1]++;
				to[i] = i + 1;
			}
		}
		int num_islands = 0;
		if (reach[0] == 1 && reach[1] == 1 && to[2] != 1) num_islands++;
		if (reach[n - 1] == 1 && reach[n - 2] == 1 && to[n - 3] != n - 2) num_islands++;
 
		for (int i = 2; i < n - 3; i++) {
			if (reach[i] == 1 && reach[i + 1] == 1 && to[i + 2] != i + 1 &&
			    to[i - 1] != i) {
				num_islands++;
			}
		}
		int num_zeros = 0;
		for (int i = 0; i < n; i++) {
			if (reach[i] == 0) { num_zeros++; }
		}
		out.print(num_zeros + num_islands);
		out.close();
	}
}

Extra (nivel Plata)

Supongamos que, en lugar de que la vaca $i$ le pase a la vaca más cercana, la vaca $i$ le pasa a la vaca $p_i$ donde el arreglo $a_1,a_2,\dots,a_N$ se da como entrada ( $1\le a_i\le N$ ). En otras palabras, el grafo de pases puede ser cualquier grafo funcional.

Resolver el problema en tiempo $O(N)$ .