Skip to Content
CTRL K

High Card Low Card (Gold)

Análisis oficial (C++) 

Explicación

Primero, notemos que podemos considerar cada mitad de las cartas de Elsie de forma independiente, y está bien reordenar cada mitad de cualquier manera (porque solo hay que emparejar cada carta de Elsie con las de Bessie).

Podemos hallar las cartas de Bessie comprobando las cartas que Elsie no tiene de 11 a 2N2N. Como la primera mitad del juego da victorias a la carta más alta y la segunda mitad del juego da victorias a la carta más baja, es óptimo que Bessie use sus N2\frac{N}{2} cartas más altas para la primera mitad y sus N2\frac{N}{2} cartas más bajas para la segunda mitad. Ahora sabemos qué cartas jugarán Bessie y Elsie en cada mitad, y necesitamos hallar la mejor estrategia de Bessie emparejando sus cartas de forma voraz.

Para carta alta, una estrategia es que Bessie juegue la carta más alta solo si es mayor que la de Elsie. En caso contrario, debería jugar su carta más baja, para guardar las cartas más altas para el futuro y no desperdiciar una carta buena. Para hacer esto, ordenamos las cartas de Bessie y de Elsie en orden decreciente. Luego, recorremos todas las cartas de Elsie y si la carta no emparejada más alta de Bessie es mayor, las emparejamos y pasamos al siguiente índice. Si no, mantenemos el índice aquí, porque potencialmente podemos emparejar esta carta con una de las siguientes de Elsie.

Otra estrategia es ordenar ambas listas de cartas en orden creciente, y para cada carta de Elsie elegir la carta más baja de Bessie que la gane. Esto se puede lograr con búsqueda binaria o dos punteros.

Para ambas estrategias, la segunda mitad (carta baja) usa la lógica inversa.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int number_of_wins(vector<int> &bessie, vector<int> &elsie,
                   function<bool(int, int)> cmp) {
	int n = size(bessie);
	assert(size(bessie) == size(elsie));
 
	sort(begin(bessie), end(bessie), cmp);
	sort(begin(elsie), end(elsie), cmp);
 
	int bpos = 0;  // índice de la carta que Bessie usa en el movimiento actual
	int wins = 0;
 
	for (int i = 0; i < n; i++) {
		// Comprobamos si Bessie puede ganar. Si no puede, usará su peor
		// carta.
		if (cmp(bessie[bpos], elsie[i])) {
			wins++;
			bpos++;
		}
	}
 
	return wins;
}
 
int main() {
	freopen("cardgame.in", "r", stdin);
	freopen("cardgame.out", "w", stdout);
 
	int n;
	cin >> n;
 
	map<int, int> elsie_has;
 
	// La primera y la segunda mitad son independientes.
	vector<int> bessie_first(n / 2), bessie_second(n / 2);
	vector<int> elsie_first(n / 2), elsie_second(n / 2);
 
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
 
		elsie_has[x] = 1;
 
		if (i < n / 2) {
			elsie_first[i] = x;
		} else {
			elsie_second[i - n / 2] = x;
		}
	}
 
	for (int i = 2 * n; i > 0; i--) {
		if (elsie_has.find(i) == elsie_has.end())  // Elsie no tiene esta carta
		{
			if (size(bessie_first) < n / 2)  // la carta más grande debe usarse en la primera mitad
			{
				bessie_first.push_back(i);
			} else {
				bessie_second.push_back(i);
			}
		}
	}
 
	int ans = 0;
 
	// En la primera mitad gana la persona con la carta de mayor valor
	ans +=
	    number_of_wins(bessie_first, elsie_first, [](int a, int b) { return a > b; });
 
	// En la segunda mitad del juego gana la persona con la carta de menor valor
	ans +=
	    number_of_wins(bessie_second, elsie_second, [](int a, int b) { return a < b; });
 
	cout << ans << endl;
}
 
import java.io.*;
import java.util.*;
 
public class HighCardGold {
	static boolean[] C;
	static List<Integer> B = new ArrayList<>();
	static List<Integer> F = new ArrayList<>();
	static List<Integer> S = new ArrayList<>();
	static int N;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("cardgame");
		N = io.nextInt();
 
		C = new boolean[2 * N + 1];
 
		for (int i = 0; i < N; i++) {
			int c = io.nextInt();
			C[c] = true;
			if (i < N / 2) F.add(c);  // Primera mitad
			else S.add(c);            // Segunda mitad
		}
 
		for (int i = 1; i < 2 * N + 1; i++) {
			if (!C[i]) B.add(i);  // Cartas de Bessie
		}
 
		// Ordenamos las cartas (B ya está ordenada)
		Collections.sort(F);
		Collections.sort(S);
 
		int ix = B.size() - 1;
		int score = 0;
		for (int i = F.size() - 1; i >= 0; i--) {
			if (F.get(i) < B.get(ix)) {
				score++;
				ix--;
			}
		}
 
		ix = 0;
		for (int i = 0; i < S.size(); i++) {
			if (B.get(ix) < S.get(i)) {
				ix++;
				score++;
			}
		}
 
		io.println(score);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
with open("cardgame.in") as read:
	N = int(read.readline())
	elsie = [int(read.readline()) for i in range(N)]
	set_elsie = set(elsie)
	# hallamos las cartas de Bessie
	bessie = [i for i in range(1, 2 * N + 1) if i not in set_elsie]
 
# hallamos las cartas que usan en ambos juegos y las ordenamos;
# es mejor usar las más altas en las primeras N/2 y las más bajas en las segundas N/2
elsie_high = sorted(elsie[: N // 2], reverse=True)
elsie_low = sorted(elsie[N // 2 :])
bessie_high = sorted(bessie[N // 2 :], reverse=True)
bessie_low = sorted(bessie[: N // 2])
wins, bessie_index = 0, 0  # llevamos las victorias y el índice de la carta de Bessie
 
# primera mitad - carta alta
for i in range(N // 2):
	# si la carta de Bessie es mayor que la de Elsie,
	# pasamos a la siguiente carta de Bessie y de Elsie; si no, Bessie puede usar su peor
	if bessie_high[bessie_index] > elsie_high[i]:
		wins += 1
		bessie_index += 1
 
# lógica invertida para carta baja
bessie_index = 0
for i in range(N // 2):
	# si la carta de Bessie es menor que la de Elsie,
	# pasamos a la siguiente carta de Bessie y de Elsie; si no, Bessie puede usar su peor
	if bessie_low[bessie_index] < elsie_low[i]:
		wins += 1
		bessie_index += 1
 
print(wins, file=open("cardgame.out", "w"))
Fundamentos