Skip to Content
CTRL K

Just Stalling

Análisis oficial (C++ y Java) 

Solución 1

Consideremos las vacas en orden descendente de altura.

Primero, nótese que el número de establos en los que podemos colocar a la vaca más alta es el número de establos con altura mayor o igual a la altura de esta vaca.

Luego, el número de establos en los que podemos colocar a la segunda vaca más alta es el número de establos al menos tan altos como esta vaca, menos uno, ya que la vaca más alta ya ocupa uno de estos establos. La observación clave aquí es que este número es independiente de en qué establo se coloca la vaca más alta (por eso ordenamos las vacas en orden descendente).

De forma similar, el número de establos en los que se puede colocar a la tercera vaca más alta es el número de establos al menos tan altos como esta vaca, menos dos, ya que las dos vacas más altas ocupan dos de estos establos.

Este patrón continúa, así que podemos calcular la respuesta simplemente multiplicando todos estos números (elecciones) entre sí.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> cows(n);
	vector<int> stalls(n);
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
	for (int i = 0; i < n; i++) { cin >> stalls[i]; }
 
	sort(cows.begin(), cows.end());
	sort(stalls.begin(), stalls.end());
 
	vector<long long> possible_places(n);
	// Creamos una lista con el número de establos que cada vaca puede usar
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (cows[i] <= stalls[j]) { possible_places[i]++; }
		}
	}
 
	long long possibilities = 1;
	/*
	 * Para cada vaca, hallamos el número de establos que puede usar en una permutación válida
	 * Usamos la fórmula de la explicación
	 * Multiplicamos el producto acumulado por este valor
	 */
	for (int i = n - 1; i >= 0; i--) {
		possibilities *= possible_places[i] - (n - i - 1);
	}
 
	cout << possibilities << endl;
}
import java.io.*;
import java.util.*;
 
public class JustStalling {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
 
		int[] cows = new int[n];
		int[] stalls = new int[n];
 
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { cows[i] = Integer.parseInt(st.nextToken()); }
 
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { stalls[i] = Integer.parseInt(st.nextToken()); }
 
		Arrays.sort(cows);
		Arrays.sort(stalls);
 
		long[] possiblePlaces = new long[n];
		// Creamos una lista con el número de establos que cada vaca puede usar
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (cows[i] <= stalls[j]) { possiblePlaces[i]++; }
			}
		}
 
		long possibilities = 1;
		/*
		 * Para cada vaca, hallamos el número de establos que puede usar en una permutación válida
		 * Usamos la fórmula de la explicación
		 * Multiplicamos el producto acumulado por este valor
		 */
		for (int i = n - 1; i >= 0; i--) {
			possibilities *= possiblePlaces[i] - (n - i - 1);
		}
 
		System.out.println(possibilities);
	}
}
n = int(input())
cows = sorted(map(int, input().split(" ")))
stalls = sorted(map(int, input().split(" ")))
 
possible_places = [0] * n
# Creamos una lista con el número de establos que cada vaca puede usar.
for i in range(n):
	for j in range(n):
		if cows[i] <= stalls[j]:
			possible_places[i] += 1
 
possibilities = 1
"""
Para cada vaca, hallamos el número de establos que puede usar en una permutación válida
Usamos la fórmula de la explicación
Multiplicamos el producto acumulado por este valor
"""
for i in range(n - 1, -1, -1):
	possibilities *= possible_places[i] - (n - i - 1)
 
print(possibilities)

Solución 2

En lugar de recorrer los establos cada vez, podemos usar dos punteros.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> cows(n);
	vector<int> stalls(n);
	for (int &c : cows) { cin >> c; }
	for (int &s : stalls) { cin >> s; }
 
	sort(cows.begin(), cows.end());
	sort(stalls.begin(), stalls.end());
 
	long long possibilities = 1;
	int j = n - 1;
	for (int i = n - 1; i >= 1; i--) {
		while (j >= 0 && stalls[j] >= cows[i]) { j--; }
		possibilities *= i - j;
	}
 
	cout << possibilities << endl;
}
import java.io.*;
import java.util.*;
 
public class JustStalling {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
 
		int[] cows = new int[n];
		int[] stalls = new int[n];
 
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { cows[i] = Integer.parseInt(st.nextToken()); }
 
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { stalls[i] = Integer.parseInt(st.nextToken()); }
 
		Arrays.sort(cows);
		Arrays.sort(stalls);
 
		long possibilities = 1;
		int j = n - 1;
		for (int i = n - 1; i >= 1; i--) {
			while (j >= 0 && stalls[j] >= cows[i]) { j--; }
			possibilities *= (i - j);
		}
 
		System.out.println(possibilities);
	}
}
n = int(input())
 
cows = list(map(int, input().split()))
stalls = list(map(int, input().split()))
 
cows.sort()
stalls.sort()
 
possibilities = 1
j = n - 1
for i in range(n - 1, 0, -1):
	while j >= 0 and stalls[j] >= cows[i]:
		j -= 1
 
	possibilities *= i - j
 
print(possibilities)
Fundamentos