Skip to Content
CTRL K

Búsqueda completa básica

Recursos
FuenteRecursoNotas
IUSACO6 - Complete Search

el módulo se basa en esto


En muchos problemas (sobre todo en Bronce) alcanza con revisar todos los casos posibles del espacio de soluciones, ya sean todos los elementos, todos los pares de elementos, todos los subconjuntos o todas las permutaciones. No es de extrañar que esto se llame búsqueda completa (complete search) (o fuerza bruta), porque busca por completo todo el espacio de soluciones.

HechoFuenteNombreDificultadTagsSolución
CFMaximum DistanceFácilen el módulo

Solución - Maximum Distance

Podemos iterar sobre cada par de puntos y calcular el cuadrado de la distancia entre ellos, elevando al cuadrado la fórmula de la distancia euclidiana:

distance[(x1,y1),(x2,y2)]2=(x2−x1)2+(y2−y1)2. \text{distance}[(x_1,y_1),(x_2,y_2)]^2 = (x_2-x_1)^2 + (y_2-y_1)^2.

Mantenemos el máximo actual del cuadrado de la distancia en max_squared.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
 
	for (int &t : x) { cin >> t; }
	for (int &t : y) { cin >> t; }
 
	int max_squared = 0;                   // guarda el máximo actual
	for (int i = 0; i < n; i++) {          // para cada primer punto
		for (int j = i + 1; j < n; j++) {  // y cada segundo punto
			int dx = x[i] - x[j];
			int dy = y[i] - y[j];
			int square = dx * dx + dy * dy;
 
			/*
			 * si el cuadrado de la distancia entre los dos puntos es
			 * mayor que nuestro máximo actual, actualizamos el máximo
			 */
			max_squared = max(max_squared, square);
		}
	}
 
	cout << max_squared << endl;
}
import java.io.*;
import java.util.*;
 
public class MaxDist {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
 
		for (int i = 0; i < n; i++) { x[i] = io.nextInt(); }
		for (int i = 0; i < n; i++) { y[i] = io.nextInt(); }
 
		int maxSquared = 0;                    // guarda el máximo actual
		for (int i = 0; i < n; i++) {          // para cada primer punto
			for (int j = i + 1; j < n; j++) {  // y cada segundo punto
				int dx = x[i] - x[j];
				int dy = y[i] - y[j];
				int square = dx * dx + dy * dy;
 
				/*
				 * si el cuadrado de la distancia entre los dos puntos es
				 * mayor que nuestro máximo actual, actualizamos el máximo
				 */
				maxSquared = Math.max(maxSquared, square);
			}
		}
 
		io.println(maxSquared);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
 
max_squared = 0  # guarda el máximo actual
for i in range(n):  # para cada primer punto
	for j in range(i + 1, n):  # y cada segundo punto
		dx = x[i] - x[j]
		dy = y[i] - y[j]
		square = dx * dx + dy * dy
 
		"""
		si el cuadrado de la distancia entre los dos puntos es
		mayor que nuestro máximo actual, actualizamos el máximo
		"""
		max_squared = max(max_squared, square)
 
print(max_squared)

Un par de observaciones:

  • Como iteramos sobre todos los pares de puntos, el bucle de jj empieza en j=i+1j = i+1 para que el punto ii y el punto jj nunca sean el mismo punto. Además, así cada par se cuenta una sola vez. En este problema no importa si contamos los pares dos veces o si permitimos que ii y jj sean el mismo punto, pero en otros problemas en los que estamos contando algo en lugar de buscar el máximo, es importante cuidar de no sobrecontar.
  • En segundo lugar, el problema pide el cuadrado de la máxima distancia euclidiana entre cualquier par de puntos. Algunos estudiantes pueden sentirse tentados a mantener la distancia máxima en una variable entera y elevarla al cuadrado al final, al imprimir. El problema es que, aunque el cuadrado de la distancia entre dos puntos enteros siempre es un entero, la distancia en sí no tiene por qué ser un entero. Así, terminaríamos metiendo un valor no entero en una variable entera, lo que trunca la parte decimal.

La siguiente solución guarda correctamente la distancia máxima en una variable de punto flotante.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
 
	for (int &t : x) { cin >> t; }
	for (int &t : y) { cin >> t; }
 
	double max_dist = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int dx = x[i] - x[j];
			int dy = y[i] - y[j];
			int square = dx * dx + dy * dy;
			max_dist = max(max_dist, sqrt(square));
		}
	}
 
	cout << (int)pow(max_dist, 2) << endl;
}

Sin embargo, igual falla en el siguiente caso de prueba (imprime 12, mientras que la respuesta correcta es 13):

2
0 3
2 0

Redondear alcanza ((int) round(pow(max_dist, 2))), pero la lección es que conviene quedarse con enteros siempre que sea posible.

La siguiente solución guarda correctamente la distancia máxima en una variable de punto flotante.

import java.io.*;
import java.util.*;
 
public class MaxDist {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
 
		for (int i = 0; i < n; i++) { x[i] = io.nextInt(); }
		for (int i = 0; i < n; i++) { y[i] = io.nextInt(); }
 
		double maxDist = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int dx = x[i] - x[j];
				int dy = y[i] - y[j];
				int square = dx * dx + dy * dy;
 
				/*
				 * si el cuadrado de la distancia entre los dos puntos es
				 * mayor que nuestro máximo actual, actualizamos el máximo
				 */
				maxDist = Math.max(maxDist, Math.sqrt(square));
			}
		}
 
		io.println((int)Math.round(Math.pow(maxDist, 2)));
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Sin embargo, igual falla en el siguiente caso de prueba (imprime 12, mientras que la respuesta correcta es 13):

2
0 3
2 0

Redondear alcanza ((int) Math.round(Math.pow(maxDist, 2))), pero la lección es que conviene quedarse con enteros siempre que sea posible.

La siguiente solución guarda correctamente la distancia máxima en una variable de punto flotante.

import math
 
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
 
max_dist = 0
for i in range(n):
	for j in range(i + 1, n):
		dx = x[i] - x[j]
		dy = y[i] - y[j]
		square = dx * dx + dy * dy
		max_dist = max(max_dist, math.sqrt(square))
 
print(int(max_dist**2))

Sin embargo, igual falla en el siguiente caso de prueba (imprime 12, mientras que la respuesta correcta es 13):

2
0 3
2 0

Redondear alcanza (round(MaxDistance ** 2)), pero la lección es que conviene quedarse con enteros siempre que sea posible.

Problemas

HechoFuenteNombreDificultadTagsSolución
BronzeMilk PailsFácilComplete SearchSolución
BronzeDiamond CollectorFácilComplete SearchSolución
BronzeDaisy ChainsFácilComplete SearchSolución
BronzeCounting LiarsNormalComplete Search, SortingSolución
Bronze★ Cow GymnasticsNormalComplete SearchSolución
Bronze★ Bovine GenomicsNormalComplete SearchSolución
BronzeTrianglesNormalComplete SearchSolución
BronzeLifeguardsNormalComplete SearchSolución
Bronze★ Why Did the Cow Cross the Road IINormalComplete SearchSolución
BronzeGuess the AnimalDifícilComplete SearchSolución
Silver★ Bovine GenomicsDifícilComplete SearchSolución
Bronze★ Load BalancingDifícilComplete SearchSolución
Bronze★ Sleeping in ClassDifícilComplete SearchSolución
Bronze★ Cow CheckupsDifícilComplete SearchSolución
BronzeContaminated MilkMuy difícilComplete SearchSolución
Bronze★ Cowntact TracingMuy difícilComplete SearchSolución
BronzeBull in a China ShopMuy difícilComplete SearchSolución
SilverLoad BalancingMuy difícilComplete SearchSolución
BronzeMoo LanguageMuy difícilComplete SearchSolución
SimulaciónBúsqueda completa con recursión