Twenty-four

Explicación

Podemos hacer una búsqueda completa de todas las formas posibles de crear una expresión aritmética con una mano de cartas. Para cada permutación de la mano, probamos todas las formas de colocar operadores aritméticos. Nótese que hay dos formas posibles de disponer los paréntesis: ((( ) ) ) o (( ) ( )), así que debemos probar ambos casos. La expresión aritmética con el valor máximo que no sea mayor que 24 es nuestra respuesta.

Complejidad temporal: $\mathcal{O}((\texttt{\# of cards})! \times (\texttt{\# of operations})^{(\texttt{\# of cards})}$

Implementación

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int ans;
int hand[4];                   // La mano de cartas dada.
vector<int> hand_permutation;  // La permutación generada de la mano de cartas.
bool chosen[4];                // Si una carta dada está presente en `hand_permutation`.
 
// Función que recibe dos números y una operación y devuelve el resultado.
int operation(int op, int num1, int num2) {
	switch (op) {
	case 0:
		return num1 + num2;
	case 1:
		return num1 - num2;
	case 2:
		return num1 * num2;
	case 3: {
		// El divisor no puede ser 0 y el cociente debe ser un número entero.
		if (num2 == 0 || num1 % num2 != 0) { return INT32_MIN; }
		return num1 / num2;
	}
	}
	return INT32_MIN;
}
 
// Función que genera todas las permutaciones posibles de la mano de cartas.
void generate_hand_permutation() {
	if (hand_permutation.size() == 4) {
		// Hemos generado una permutación, así que podemos intentar colocar los
		// operadores.
		for (int op1 = 0; op1 < 4; op1++) {
			for (int op2 = 0; op2 < 4; op2++) {
				for (int op3 = 0; op3 < 4; op3++) {
					int first =
					    operation(op1, hand_permutation[0], hand_permutation[1]);
					// Si la operación es inválida, continue;
					if (first == INT32_MIN) { continue; }
 
					int second = operation(op2, first, hand_permutation[2]);
					if (second == INT32_MIN) { continue; }
 
					int third = operation(op3, second, hand_permutation[3]);
					if (third == INT32_MIN) { continue; }
 
					if (third <= 24) { ans = max(ans, third); }
				}
			}
		}
 
		// Caso 2: (( ) ( ))
		for (int op1 = 0; op1 < 4; op1++) {
			for (int op2 = 0; op2 < 4; op2++) {
				for (int op3 = 0; op3 < 4; op3++) {
					int first =
					    operation(op1, hand_permutation[0], hand_permutation[1]);
					if (first == INT32_MIN) { continue; }
 
					int second =
					    operation(op2, hand_permutation[2], hand_permutation[3]);
					if (second == INT32_MIN) { continue; }
 
					int third = operation(op3, first, second);
					if (third == INT32_MIN) { continue; }
 
					if (third <= 24) { ans = max(ans, third); }
				}
			}
		}
	} else {
		// En caso contrario, seguimos construyendo nuestro arreglo de permutación.
		for (int i = 0; i < 4; i++) {
			if (chosen[i]) continue;
			chosen[i] = true;
			hand_permutation.push_back(hand[i]);
			generate_hand_permutation();
			chosen[i] = false;
			hand_permutation.pop_back();
		}
	}
}
 
int main() {
	int num_hands;
	cin >> num_hands;
 
	for (int h = 0; h < num_hands; h++) {
		ans = INT32_MIN;
		for (int i = 0; i < 4; i++) { cin >> hand[i]; }
 
		// Empezamos la búsqueda completa.
		generate_hand_permutation();
		cout << ans << "\n";
	}
}


import java.io.*;
import java.util.*;
 
public class Solution {
	static int ans;
	// La mano de cartas dada.
	static int[] hand = new int[4];
	// La permutación generada de la mano de cartas.
	static List<Integer> handPermutation = new ArrayList<>();
	// Si una carta dada está presente en `hand_permutation`.
	static boolean[] chosen = new boolean[4];
 
	// Función que recibe dos números y una operación y devuelve el
	// resultado.
	static int operation(int op, int num1, int num2) {
		switch (op) {
		case 0:
			return num1 + num2;
		case 1:
			return num1 - num2;
		case 2:
			return num1 * num2;
		case 3: {
			// El divisor no puede ser 0 y el cociente debe ser un entero.
			if (num2 == 0 || num1 % num2 != 0) { return Integer.MIN_VALUE; }
			return num1 / num2;
		}
		}
		return Integer.MIN_VALUE;
	}
 
	// Función que genera todas las permutaciones posibles de la mano de cartas.
	private static void generateHandPermutation() {
		if (handPermutation.size() == 4) {
			// Hemos generado una permutación, así que podemos intentar colocar los
			// operadores.
			// Caso 1: ((( ) ) )
			for (int op1 = 0; op1 < 4; op1++) {
				for (int op2 = 0; op2 < 4; op2++) {
					for (int op3 = 0; op3 < 4; op3++) {
						int first = operation(op1, handPermutation.get(0),
						                      handPermutation.get(1));
						// Si la operación es inválida, continue;
						if (first == Integer.MIN_VALUE) { continue; }
 
						int second = operation(op2, first, handPermutation.get(2));
						if (second == Integer.MIN_VALUE) { continue; }
 
						int third = operation(op3, second, handPermutation.get(3));
						if (third == Integer.MIN_VALUE) { continue; }
 
						if (third <= 24) { ans = Math.max(ans, third); }
					}
				}
			}
 
			// Caso 2: (( ) ( ))
			for (int op1 = 0; op1 < 4; op1++) {
				for (int op2 = 0; op2 < 4; op2++) {
					for (int op3 = 0; op3 < 4; op3++) {
						int first = operation(op1, handPermutation.get(0),
						                      handPermutation.get(1));
						if (first == Integer.MIN_VALUE) { continue; }
 
						int second = operation(op2, handPermutation.get(2),
						                       handPermutation.get(3));
						if (second == Integer.MIN_VALUE) { continue; }
 
						int third = operation(op3, first, second);
						if (third == Integer.MIN_VALUE) { continue; }
 
						if (third <= 24) { ans = Math.max(ans, third); }
					}
				}
			}
		} else {
			// En caso contrario, seguimos construyendo nuestro arreglo de permutación.
			for (int i = 0; i < 4; i++) {
				if (chosen[i]) continue;
				chosen[i] = true;
				handPermutation.add(hand[i]);
				generateHandPermutation();
				chosen[i] = false;
				handPermutation.remove(handPermutation.size() - 1);
			}
		}
	}
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num_hands = sc.nextInt();
 
		for (int h = 0; h < num_hands; h++) {
			ans = Integer.MIN_VALUE;
			for (int i = 0; i < 4; i++) { hand[i] = sc.nextInt(); }
 
			// Empezamos la búsqueda completa.
			generateHandPermutation();
			System.out.println(ans);
		}
	}
}


ans = 0
hand = [0] * 4  # La mano de cartas dada.
hand_permutation = []  # La permutación generada de la mano de cartas.
chosen = [False] * 4  # Si una carta dada está presente en `hand_permutation`.
 
# Función que recibe dos números y una operación y devuelve el resultado.
def operation(op, num1, num2):
	if op == 0:
		return num1 + num2
	elif op == 1:
		return num1 - num2
	elif op == 2:
		return num1 * num2
	else:
		# El divisor no puede ser 0 y el cociente debe ser un número entero.
		if num2 == 0 or num1 % num2 != 0:
			return float("-inf")
		return num1 // num2
 
 
# Función que genera todas las permutaciones posibles de la mano de cartas.
def generate_hand_permutation():
	global ans
 
	if len(hand_permutation) == 4:
		# Hemos generado una permutación, así que podemos intentar colocar los operadores.
		for op1 in range(4):
			for op2 in range(4):
				for op3 in range(4):
					first = operation(op1, hand_permutation[0], hand_permutation[1])
					# Si la operación es inválida, continue;
					if first == float("-inf"):
						continue
 
					second = operation(op2, first, hand_permutation[2])
					if second == float("-inf"):
						continue
 
					third = operation(op3, second, hand_permutation[3])
					if third == float("-inf"):
						continue
 
					if third <= 24:
						ans = max(ans, third)
 
		# Caso 2: (( ) ( ))
		for op1 in range(4):
			for op2 in range(4):
				for op3 in range(4):
					first = operation(op1, hand_permutation[0], hand_permutation[1])
					if first == float("-inf"):
						continue
 
					second = operation(op2, hand_permutation[2], hand_permutation[3])
					if second == float("-inf"):
						continue
 
					third = operation(op3, first, second)
					if third == float("-inf"):
						continue
 
					if third <= 24:
						ans = max(ans, third)
	else:
		# En caso contrario, seguimos construyendo nuestro arreglo de permutación.
		for i in range(4):
			if chosen[i]:
				continue
			chosen[i] = True
			hand_permutation.append(hand[i])
			generate_hand_permutation()
			chosen[i] = False
			hand_permutation.pop()
 
 
for _ in range(int(input())):
	ans = float("-inf")
	for i in range(4):
		hand[i] = int(input())
 
	# Empezamos la búsqueda completa.
	generate_hand_permutation()
	print(ans)